Simulating finite automata with context-free grammars. (Q1853167)

We consider simulating finite automata (both deterministic and nondeterministic) with context-free grammars in Chomsky Normal Form (CNF). We show that any unary DFA with \(n\) states can be simulated by a CNF grammar with \(O(n^{1/3})\) variables, and this bound is tight. We show that any unary NFA with \(n\) states can be simulated by a CNF grammar with \(O(n^{2/3})\) variables. Finally, for larger alphabets we show that there exist languages which can be accepted by an \(n\)-state DFA, but which require \(\Omega(n/\log n)\) variables in any equivalent CNF grammar.