We changed our privacy policy. Read more.

New answers tagged


No, the exponential lower bound for determinization holds already for unambiguous NFAs. This is obtained as follows: Consider the alphabet $\{a,b\}$, and the language: $$L_k=\{w\in \{a,b\}^*:\text{the $k$-th before last letter in }w\text{ is }b\}$$ It's easy to construct an unambiguous NFA for $L_k$: the NFA guesses when the $k$ before last letter is, and ...

Top 50 recent answers are included