Simulating finite automata with context-free grammars.
type: Item
instance of: scholarly article
title: Simulating finite automata with context-free grammars.
zbMATH Open document ID: 1042.68060
DOI: 10.1016/S0020-0190(02)00316-2
author: Michael Domaratzki
author: Giovanni Pighizzini
author: Jeffrey Shallit
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 1856497
zbMATH Keywords: Formal languages
zbMATH Keywords: Context-free grammar
zbMATH Keywords: Finite automata
Wikidata QID: Q61677530
MaRDI profile type: Publication
cites work: Tight lower bounds on the length of word chains
cites work: On the length of word chains
cites work: Intersection and union of regular languages and state complexity
cites work: Finite automata and unary languages
cites work: Q4939575
cites work: Q5834367
cites work: A pushdown automaton or a context-free grammar - which is more economical?
cites work: Normal Recurring Decimals
cites work: Q5541336
cites work: Some classifications of context-free languages
cites work: Q4105792
cites work: Q5592246
cites work: UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
cites work: Q4531381
cites work: The state complexities of some basic operations on regular languages
DBLP publication ID: journals/ipl/DomaratzkiPS02
Recommended article: An efficient automata approach to some problems on context-free grammars.
Recommended article: Q4371017
Recommended article: Q4418597
Recommended article: Finite nondeterministic automata: simulation and minimality
Recommended article: Q6100191
Recommended article: Q4782102
Recommended article: Simulation algorithms for symbolic automata
Recommended article: Limited automata and context-free languages
description: scientific article; zbMATH DE number 1856497