I think I know how to convert a regular expression to NFA without requiring epsilon transitions, but I'm not sure if I'm right (I'm just using common sense to be honest, no particular algorithm in my head). Is there a general algorithm for this without requiring epsilon transitions?

For example, if I consider the expression: $a(abb)^* + b$, I obtain the following NFA: enter image description here

Would this be correct? Basically, the $b$ part in the union is clear, need to go to an accept state with symbol $b$. For the first part, we need to take a transition with $a$ and then an empty string is possible, so $q_2$ is an accept state. After the empty string, one can take $abb$, so that needs to be in a loop with $q_2$. Am I missing something? I somehow find it easier than the standard algorithm with epsilon transitions, but I'm not sure whether my approach is correct, or if it doesn't work in some cases! Any explanation (or redirection to an algorithm/material) would be helpful!

  • $\begingroup$ Why don't you simply follow the standard process of RE to NFA construction and remove all epsilon transitions from it? $\endgroup$
    – codeR
    Commented Apr 18 at 11:08

1 Answer 1


You can convert the regular expression into an automaton using the Glushkov's construction.

The resulting automaton is non-deterministic and does not contain any $\varepsilon$-transition. Its number of states is one plus the number of letters in the regular expression.

Alternatively, you can convert the regular expression into an $\varepsilon$-automaton using Thompson's construction, then remove the $\varepsilon$-transitions using the forward or backward closure. The number of states is the double of the number of symbols in the regular expression, so it is more than double the size of Glushkov's automaton.


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.