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.