This question already has an answer here:

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.


marked as duplicate by David Richerby, FrankW, Rick Decker, D.W., Juho Oct 26 '14 at 12:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


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$ – Hendrik Jan Oct 25 '14 at 11:58

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