I have the following DFA. (Yellow stated are accepting states.) I want to eliminate states step by step to find the regular expression of it.
In my steps, I think there is a bug because I do not know what to do with state 4.

enter image description here

If you know how to convert this DFA to regular expression please help me.


1 Answer 1


From state 4 you cannot reach an accepting state. That means that state 4 does not contribute to the language of the automaton. Therefore you can simply delete it and then apply the state elimination procedure to the rest of the automaton to find the equivalent regular expression.

  • $\begingroup$ Additionally, it is convenient to have a single initial and a single final state. The target of the elimination procedure then is the reduce the automaton to a single edge from initial to final (with expression that captures the automaton). This is obtained by adding two new states, and $\varepsilon$-edges to/from the old initial/final states from/to the new initial/final state. $\endgroup$ Oct 25, 2014 at 11:58

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