7
$\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

Improve this question
$\endgroup$
2
  • 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, 2014 at 9:31
  • 2
    $\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, 2015 at 3:53

3 Answers 3

Reset to default
8
$\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.

Improve this answer
$\endgroup$
0
2
$\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$.

Improve this answer
$\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

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ What does this add over older answers? Also, I find your post hard to follow. $\endgroup$
    – Raphael ♦
    Jan 22, 2017 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, 2017 at 5:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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