# Determinising unambiguous automata without exponential blowup

Is it possible to determinise unambiguous finite automata without exponential blowup in the number of states? I think it should not be possible but I am unable to come up with counterexamples.

• I think you cannot (at least you cannot avoid super-polynomial blowup). See: arxiv.org/abs/1711.03993 Sep 19 at 10:20

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 then proceeds with verifying that the current letter is $$b$$, and that there are exactly $$k$$ letters remaining. This NFA has size $$O(k)$$.

However, to construct a DFA for $$L_k$$, you must keep in memory the last $$k$$ letters, yielding at least $$2^{k}$$ states.

• For the sake of precision, what is $w$, a string from $\{a,b\}*$? Sep 19 at 22:21
• Also this is the exact example given in the Wikipedia page for Unambiguous Finite Automata, with some more helpful explanations there. Sep 20 at 3:04
• @chepner - Yes. I'll add a clarification Sep 20 at 9:14
• $k+1$ states suffice, so this is nearly optimal. Sep 20 at 17:57