I'm using Thompson's algorithm to convert from a regular expression to a NFA. Is Thompson's algorithm guaranteed to always output a minimal NFA, i.e., a NFA with the smallest possible number of states?
For instance, consider this example. I have the regular expression $(a|b)$. According to this website, Thompson's algorithm converts it to the following NFA:
o--->o
/ε a \ε
>o O
\ε b /ε
o--->o
However, the following NFA is smaller and seems like it would also be equivalent:
o
a/ \ε
>o O
b\ /ε
o
Why doesn't Thompson's algorithm output the latter NFA? What did I miss here? Is that Thompson's construction algorithm not optimized at all?
a
transition and ab
transition between them. $\endgroup$