MAGIC NUMBERS AND TERNARY ALPHABET
Galina Jirásková · International Journal of Foundations of Computer Science · 2011
A number α, in the range from n to 2 n , is magic for n with respect to a given alphabet size s, if there is no minimal nondeterministic finite automaton of n states and s input symbols whose equivalent minimal deterministic finite automaton has α states. We show that in the case of a ternary alphabet, there are no magic numbers. For all n and α satisfying n ⩽ α ⩽ 2 n , we define an n-state nondeterministic finite automaton with a three-letter input alphabet that requires exactly α deterministic states.