Question

Consider the NFA N with states labeled q1, q2 and q3, where q1 is the start state and q2 and q3 are the final (accepting) states.

The transition function for N is δ(q1,a) = {q1}, δ(q1,b) = {q1,q2},  δ(q2,a) = {q3}, δ(q2,b)= ∅, δ(q3,a)= ∅, and δ(q3,b)= ∅.

Let L be the language recognized by N i.e. L(N).

a) Draw the state diagram for N.

b) Describe in plain English what's in the language L.

c) Via the construction NFA to DFA, draw the state diagram for a DFA corresponding to the NFA. Your DFA should recognize the same language L that the NFA recognizes. Remember, each state of your DFA will be labeled by a set of states from the original NFA.

e) Give a regular expression that describes L. You don't need to use any particular method to get the regular expression. (It's OK to just write the expression without justification.)

A picture upload is fine if easier!

Answer 1

; 9. intial state There are total 3 states 91, 92, 92 qe, 93 final states s(q,, a) = {qi} Slai, b)= {21990} S(92, a) = {93} S (92, b) = 0 S (9, a) = 6 S (93, 6) = 0 (a) STATE DIAGRAM :- Qab 29 (93 NEAS (b.) The language accepted by NFA should contain atleast one "b". Table for States Juput Symbol Now lets take a trop state "T" 9 {9,} {91,9,} for o transition. 92 {qo} 9 93 4 b Б

Equivalent DFA table Tuput Symbol States a b Ь 912 т T b Ь 912 93 912 91 93 T 913 9. T T b T T 912 912 T T 913 T DFA for giren NFA States 92, 93, T are not connected to intial state via direct / indirect mode i are of use and are discarded (e.) Regular expression is being derived from Arden's Theorem. (ice R=p+RoQ = P.Q*) RiE for giren question is :- R.E. 92t 913 a*b (aaa*b+ b + ab)* + a*b (d aa* b + b + ab)*b =[a+b(a aakb+b+ ab)"). [e+b]