Article Title：Simulating finite automata with context-free grammars
Abstract：
We consider simulating finite automata (both deterministic and nondetenninistic) with context-free grammars in Chomsky normal form (CNTF). 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. (C) 2002 Published by Elsevier Science B.V.
Keywords: formal languages; context-free grammar; finite automata
DOI: 10.1016/S0020-0190(02)00316-2
Source：INFORMATION PROCESSING LETTERS
Welcome to correct the error, please contact email: humanisticspider@gmail.com
