regexcompiler-constructionfinite-automatanfa
Converting RE -> NFA
I have a question regarding the conversion of regular expressions to non-deterministic finite state automata:
Convert (a*|b*)* to NFA. My attempt is as follows:
Am I completely off the mark? Or somewhat there?
NB E => ε
Solution
Your NFA matches the same language as (a*|b*)*, so the answer is correct.
However, there are many NFAs that match the same language and in your case it would be possible to remove at least three epsilon arrows. Still, it will not be more correct than your suggestion.
The regex (a*|b*)* can also be simplified, without changing the semantics. E.g. (a|b)* is equivalent to (a*|b*)*. And if you think about it, the FA can be as simple as this:
