Simulating finite automata with context-free grammars.

DOI10.1016/S0020-0190(02)00316-2zbMath1042.68060WikidataQ61677530 ScholiaQ61677530MaRDI QIDQ1853167

Michael Domaratzki, Giovanni Pighizzini, Jeffrey O. Shallit

Publication date: 21 January 2003

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

Finite automata; Formal languages; Context-free grammar

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q42: Grammars and rewriting systems

Related Items

Chrobak Normal Form Revisited, with Applications, Finite state complexity, A new algorithm for regularizing one-letter context-free grammars., Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth, Descriptional Complexity of Input-Driven Pushdown Automata, DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES, Deterministic Pushdown Automata and Unary Languages

Cites Work

• Tight lower bounds on the length of word chains
• Finite automata and unary languages
• On the length of word chains
• A pushdown automaton or a context-free grammar - which is more economical?
• Intersection and union of regular languages and state complexity
• The state complexities of some basic operations on regular languages
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Some classifications of context-free languages
• Normal Recurring Decimals
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item