Question & Answer: For alphabet {p,q,r}, all strings that contain the substring rqr or end with pp……

For alphabet {p,q,r}, all strings that contain the substring rqr or end with pp.

(1) Write a regular expression for the language.

(2) Define a finite state machine (FSM) that recognizes words in the language (input alphabet, states, start state, state transition table, and accept states). Include a state digraph for the FSM.

Expert Answer

 

(1)  regular expression for the language that contain the substring rqr or end with pp —->

((p|q|r)*rqr(p|q|r)*)|(p|q|r)*pp

(2) Finite state machine (FSM) that recognizes words in the language have

input alphabet —–> p,q,r

states —————–>0,1,2,3,4,5,6,7,8,9,10,11,12,13,14

start state————->p,q,r

accept states——->4,7,8,9,10,11,12,13,14

state transition table ———->

state/input p q r
0 1 2 3
1 4 2 3
2 5 2 3
3 5 6 3
4 7 2 3
5 7 2 3
6 5 2 8
7 7 2 3
8 9 10 11
9 12 11
10 9 13 14
11 9 10 11
12 12 13 11
13 11
14 9 10 11

State digraph for the FSM———–>

DFA for ((p|q|r)*rqr(p|q|r)*)|((p|q|r)*pp)

Still stressed from student homework?
Get quality assistance from academic writers!