Converting Regular Expression to Finite Automata

Question

I am studying "Theory of Computation" by Michael Sipser. I am studying the section where he teaches how to convert "RE to FA". He uses empty transitions for union, concat and star, but that is very getting very confusing for me

But i found this another method here: https://www.codingninjas.com/codestudio/library/conversion-of-regular-expressions-to-finite-automata

This method does not use empty transitions for union, concat and star.

I am more biased towards the second method, without the empty transitions for regular opoerations.

Do both of the methods yield the same result? that is accept the language described by the RE?

Answer 1

The construction that you show from the book of Sipser is known as Thompson’s construction, building a nondeterministic automaton with $\varepsilon$-transitions. Those empty transitions can be removed by a simple algorithm, and then the automaton can be determinized, if needed. (But that can lead to an explosion in the number of states.)

Sometimes determinization is not needed at al. One can for instance use the general automaton for pattern matching.

There is a slightly more invoved algorithm that avoids $\varepsilon$-transitions. It is called Glushkov Construction, and it carefully considers incoming and outgoing transitions from initial and final states. Hence it is more involved than Thompson's.

The website algorithm you cite is nice for intuition, but quite useless for actual implementation. I cannot see what we should do with the expression $a^*b^*$. It cannot be two letters $a$ and $b$ on the same state, can it?