Question

1.Calculate a regular expression corresponding to the following DFA, available at the jflap.org website, by the method of solving a system of simultaneous equations in standard form. q0 is indicated as the initial state.

go q1 q2

2.Convert your regular expression to an NFA using the procedure of Hopcroft and Ullman

3.Convert the NFA - to a DFA.

Answer 1

The corresponding equation system is Q_0 = aQ_0 U bQ_1 Q_1 = aQ_2 U element of Q_2 = aQ_0 U bQ_1 Now plug the third equation into 2nd Q_1 = aQ_2 U element of becomes Q_1 = a(aQ_0 U bQ_1) U element of Q_1 = aaQ_0 U abQ_1 U element of Q_1 = (ab)^H (aaQ_0) U element of For the last step we apply Arden's Lemma with L = Q_1 U = ab V = aaQ_0 \r\n Now we plug the result into the first equation Q_0 = aQ_0 U bQ_1 = aQ_0 U b(ab)^H (aaQ_0)U element of) = (a U b(ab)^H aa) Q_0 U element of = (a U b (ab)^H aa)^H (By Arden's Lemma) Then we have found a regular expression for the language accepted by above automation, namely (a + b(ab)^H aa)^H \r\n Corresponding NFA NFA to DFA State table for NFA State table for the corresponding DFA State table are same, hence of a is similar