# Tag Info

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 ...