Abstract of Paper |

*A Family of NFA's which Need $2^n-\alpha$ Deterministic States*

by Kazuo Iwama, Akihiro Matsuura and Mike Paterson

**Abstract:**

We show that for any positive integers $\alpha$ and $n$ such that $\alpha \leq 2n-2$, there exists an $n$-state nondeterministic finite automaton that is equivalent to a deterministic finite automaton which needs exactly $2^{n}-\alpha$ states if $\alpha$ and $n$ satisfy some coprimality condition.