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.
1
-
1$\begingroup$ I think you cannot (at least you cannot avoid super-polynomial blowup). See: arxiv.org/abs/1711.03993 $\endgroup$– Bartosz BednarczykSep 19, 2021 at 10:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
-
$\begingroup$ For the sake of precision, what is $w$, a string from $\{a,b\}*$? $\endgroup$– chepnerSep 19, 2021 at 22:21
-
$\begingroup$ Also this is the exact example given in the Wikipedia page for Unambiguous Finite Automata, with some more helpful explanations there. $\endgroup$– justhalfSep 20, 2021 at 3:04
-
-
$\begingroup$ $k+1$ states suffice, so this is nearly optimal. $\endgroup$ Sep 20, 2021 at 17:57