6
$\begingroup$

In this old exam-task I don't understand all the steps to convert the DFA below to a Regular Expression. The $q_2$ state is eliminated first. The provided solution to eliminate $q_2$ is:

If we first eliminate $q_2$ we obtain an intermediate automata with $3$ states $(q_0$,$q_1,q_3)$ such that:

  1. We go from $q_0$ to $q_1$ with RE $a+ba$
  2. We go from $q_0$ to $q_3$ with RE $bb$
  3. We go from $q_1$ to $q_1$ with RE $ba$
  4. We go from $q_1$ to $q_3$ with RE $a+bb$

I don't understand nr2. $q_3$ can also be reached using RE $aa$. Why is this left out?

enter image description here

:

enter image description here

:

enter image description here

$\endgroup$
  • 2
    $\begingroup$ The book Introduction to Automata Theory, Languages, and Computation by Hopcroft, Ullman, Motwani describes this method of conversion of a DFA to a regular expression in detail. It is a very convenient method but requires some practice. $\endgroup$ – lgidwani Jul 21 '14 at 9:31
  • $\begingroup$ Also, as an aside. The last image looks wrong and the final regular expression should be: bb + (a+ba)(ba)*(a+bb) since in the second image, q1 is looping on (ba) $\endgroup$ – Int_Casting Feb 19 '15 at 3:53
6
$\begingroup$

The conversion in each step forms REs that describe

  • The previous direct edge from one state to another and
  • the path(s) that use(s) only the removed state as an intermediate state.

In your example, the path for $aa$ goes through $q_1$, which is not removed in this step. Thus it is not added to the RE.

$\endgroup$
1
$\begingroup$

The RE "aa" is not left out. First "a" in transaction between $q_0$ and $q_1$, second "a" between q1 and q3. Since this pair of transitions doesn't involve $q_2$ we don't consider it in the first stage of the algorithm, where we're eliminating $q_2$.

$\endgroup$
-2
$\begingroup$

it is not left out , see q3 cn still be reachable using "aa" from intial state q1 , just tk 2nd term from unioned terms and then pick 'a' from (a+ba) , tk (ba)* as NULL String and then take 2nd 'a' from (a+bb) : so by concatenation we got "aa" and we reached final state q3

$\endgroup$
  • 3
    $\begingroup$ What does this add over older answers? Also, I find your post hard to follow. $\endgroup$ – Raphael Jan 22 '17 at 18:57
  • $\begingroup$ first of all u ve made a mistake in a question. you ve changed the order of a loop at state q1 , it is supposed to be (ba)* and not (ab)* , then i pointed out a simpler way to show you tht "aa" isnt left out , directly from the regular expression you got at the last $\endgroup$ – tolani Jan 24 '17 at 5:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.