NFA for a regular expression without $\epsilon$-transitions

Question

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:

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!

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.