3
$\begingroup$

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.

$\endgroup$
1
12
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ For the sake of precision, what is $w$, a string from $\{a,b\}*$? $\endgroup$
    – chepner
    Sep 19 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$
    – justhalf
    Sep 20 at 3:04
  • $\begingroup$ @chepner - Yes. I'll add a clarification $\endgroup$
    – Shaull
    Sep 20 at 9:14
  • $\begingroup$ $k+1$ states suffice, so this is nearly optimal. $\endgroup$ Sep 20 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.