So I have a DFA which I would like to convert to a regular expression. As you can see it has multiple accepting states and the start state has incoming input 'a' from q2 and 'b' from q4.


I want to convert this into a regular expression using State elimination, and I know that I need to first create a new state call it 's' which replaces q0 as the start state, and then create another new state (call it 'f') which will be the new final state, and make q1, q2, q3, and q4 non-accepting states, and make epsilon transitions from the former accepting states to the new final state.

My question is, when I eliminate say q1, I don't know what the regular expression will be as a result. Now since q1 has 2 outgoing transitions 'a' to a2 and epsilon to f, what would be that regular expression? I know that for q2 it would be a(ba)a(ba) ... then q0 to f will be a(ba)*.. so far it doesn't make sense to me how this will end up becoming the correct regular expression. Am I on the right track?


2 Answers 2


When I eliminate say $q_1$, ..., now since $q_1$ has 2 outgoing transitions, '$a$' to $q_2$ and $\epsilon$ to $f$, what would be that regular expression?

Here are the transitions among the neighbors of $q_1$, which are $q_0, q_2$ and $f$ when $q_1$ is eliminated.

  • $\delta(q_0, ab)=q_0$
  • $\delta(q_0, aa)=q_2$
  • $\delta(q_0, a)=f$
  • $\delta(q_2, a+bb)=q_0$
  • $\delta(q_2, ba)=q_2$
  • $\delta(q_2, \epsilon+b)=f$

$a(ba)^* + a(ba)^*a(ba)^*(aa(ba)^*a(ba)^*)^* + b(ab)^* + b(ab)^*b(ab)^*(bb(ab)^*b(ab)^*)*$

I am afraid the above is not correct since it does not include $abbaa$ nor $abbab$


My final answer was:

a(ba)* + a(ba)*a(ba)*(aa(ba)*a(ba)*)* + b(ab)* + b(ab)*b(ab)*(bb(ab)*b(ab)*)*

Just checking if it's right

  • $\begingroup$ So, does it answer the question or you are not sure? $\endgroup$
    – Evil
    Feb 14, 2019 at 16:56
  • 3
    $\begingroup$ Please only use the 'answer' box if you are confident in your answer. Please don't use it to write a tentative answer and ask us whether it is correct. $\endgroup$
    – D.W.
    Feb 14, 2019 at 20:45

Your Answer

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

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