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 Ω(n/logn) variables in any equivalent CNF grammar.
Simulating finite automata with context-free grammars / M. Domaratzki, G. Pighizzini, J. Shallit. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - 84:6(2002 Dec), pp. 339-344.
Simulating finite automata with context-free grammars
G. PighizziniSecondo
;
2002
Abstract
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 Ω(n/logn) variables in any equivalent CNF grammar.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
