Unluckily there are regular languages where you can prove that the number of required states of a DFA is exponential in the input length of the regular expressi

Unluckily there are regular languages where you can prove that the number of required states of a DFA is exponential in the input length of the regular expression describing it. That's why one should use NFAs for parsing REs, see https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html For an example of such a regular expression, consider [ab]*a[ab][ab]...[ab][ab] where the number of [ab] at the end is n-1. Then any DFA for this regular expression needs at least 2^n states, while there exists an NFA using only n+1 states (the proof is an easy exercise that any Computer Science student should easily be able to do on a whiteboard ;-) ).