On a Family of Nondeterministic Finite Automata
Hing Leung · Journal of automata, languages and combinatorics · 2000
In this paper, we study the succinctness properties of a family of one-way $n$-state nondeterministic finite automata $A_n$ over a two-letter alphabet. It is shown ([4], [5]) that the smallest equivalent deterministic finite automaton has $2^n$ states, the smallest equivalent polynomially ambiguous nondeterministic finite automaton has $2^n - 1$ states, and any equivalent nondegenerate sweeping automaton has at least $2^n$ states. We conjecture that the family $A_n$ can be used to show that the complexity class L (deterministic logarithmic space) is properly contained in NL (nondeterministic logarithmic space), and any equivalent two-way deterministic finite automaton would require an exponential number of states.