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.
Simulating finite automata with context-free grammars / M. Domaratzki, G. Pighizzini, J. Shallit. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - 84:6(2002), pp. 339-344. [10.1016/S0020-0190(02)00316-2]
Simulating finite automata with context-free grammars
G. PighizziniSecondo
;
2002
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.
| File | Dimensione | Formato | |
|---|---|---|---|
|
1-s2.0-S0020019002003162-main.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
77.61 kB
Formato
Adobe PDF
|
77.61 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
