I'm new to regular expressions and I'm currently working on some exercises on converting DFA's and NFA's into their equivalent regular expressions.

I have the following NFA: enter image description here

I'm using the state elimination method to obtain the regular expression for the NFA. So I first introduced two new states, $q_{start}$ (the new start state of the NFA) and $q_{end}$ (the new and only accepting state of the NFA). After that, I eliminated the states one after the other.

To eliminate the states, I pick a state $p_e$ to be eliminated. Then for every pair $(p_1,p_2)$ with $p_1, p_2 \neq p_e$ and transitions from $p_1$ to $p_e$ and from $p_e$ to $p_2$, I determine the labels $r_0,r_1,r_2,r_3$ of this general automaton

enter image description here

wipe out $p_e$ and replace $(p_1,r_0,p_2)$ with $(p_1,r_0+r_1 r^{*}_2r_3,p_2)$.

I already eliminated states $q_0$ and $q_1$, but I have no idea how to eliminate state $q_4$, since it has no outgoing transitions except to itself. Could you please help me out with that?


1 Answer 1


Technically it can be reduced, by introducing a regular expression for the empty set, which represents the missing edge.

However, $q_4$ is completely useless for the language. They can be dropped without changing the accepted language. That should save some work.

  • $\begingroup$ So I just don't need to consider $q_4$ at all? $\endgroup$
    – Said Savci
    Commented May 12, 2015 at 21:39
  • $\begingroup$ Yes, that is my message. There is no computation from initial state to final state that will pass $q_4$. Hence it is useless, and can be dropped (deleted) without changing the language. $\endgroup$ Commented May 12, 2015 at 22:15

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.