<p>No, the exponential lower bound for determinization holds already for unambiguous NFAs. This is obtained as follows:
Consider the alphabet <span class="math-container">$\{a,b\}$</span>, and the language:
<span class="math-container">$$L_k=\{w\in \{a,b\}^*:\text{the $k$-th before last letter in }w\text{ is }b\}$$</span>
It's easy to construct an unambiguous NFA for <span class="math-container">$L_k$</span>: the NFA guesses when the <span class="math-container">$k$</span> before last letter is, and then proceeds with verifying that the current letter is <span class="math-container">$b$</span>, and that there are exactly <span class="math-container">$k$</span> letters remaining. This NFA has size <span class="math-container">$O(k)$</span>.</p>
<p>However, to construct a DFA for <span class="math-container">$L_k$</span>, you must keep in memory the last <span class="math-container">$k$</span> letters, yielding at least <span class="math-container">$2^{k}$</span> states.</p>

CC BY-SA 4.0
2021-09-19T22:21:59.417Z
For the sake of precision, what is $w$, a string from $\{a,b\}*$?
chepner
CC BY-SA 4.0
2021-09-20T03:04:14.127Z
Also this is the exact example given in the Wikipedia page for [Unambiguous Finite Automata](https://en.wikipedia.org/wiki/Unambiguous_finite_automaton), with some more helpful explanations there.
justhalf
CC BY-SA 4.0
2021-09-20T09:14:50.407Z
@chepner - Yes. I'll add a clarification
Shaull
CC BY-SA 4.0
2021-09-20T17:57:18.160Z
$k+1$ states suffice, so this is nearly optimal.
Yuval Filmus
CC BY-SA 4.0
2021-09-19T10:39:08.270Z
2021-09-20T09:15:12.233Z
2021-09-20T09:15:12.233Z
Shaull
<p>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.</p>

CC BY-SA 4.0
2021-09-19T10:20:14.070Z
I think you cannot (at least you cannot avoid super-polynomial blowup). See: https://arxiv.org/abs/1711.03993
Bartosz Bednarczyk
<fl.formal-languages><automata-theory>
Determinising unambiguous automata without exponential blowup
Arka
# Determinising unambiguous automata without exponential blowup

(Asked by: username_0 on 2021-09-19)

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.

**Tags:** fl.formal-languages, automata-theory

> **Comments:**
> **username_1**: I think you cannot (at least you cannot avoid super-polynomial blowup). See: https://arxiv.org/abs/1711.03993  

---

## 1 answers

### Answer by username_2 on 2021-09-19. Score: 12

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.

> **Comments:**
> **username_3**: For the sake of precision, what is $w$, a string from $\{a,b\}*$?  
> **username_4**: Also this is the exact example given in the Wikipedia page for [Unambiguous Finite Automata](https://en.wikipedia.org/wiki/Unambiguous_finite_automaton), with some more helpful explanations there.  
> **username_2**: @username_3 - Yes. I'll add a clarification  
> **username_5**: $k+1$ states suffice, so this is nearly optimal.  

---

