From regular expressions to deterministic finite automata: $2^{\frac{n}{2}+\sqrt{n}(\log n{)}^{\Theta (1)}}$ states are necessary and sufficient

Olga Martynova, Alexander Okhotin

It is proved that every regular expression of alphabetic width $n$, that is, with $n$ occurrences of symbols of the alphabet, can be transformed into a deterministic finite automat…