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 automataFormal languagesContext-free grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (8)

Descriptional Complexity of Input-Driven Pushdown Automata ⋮ Two-way machines and de Bruijn words ⋮ A new algorithm for regularizing one-letter context-free grammars. ⋮ Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth ⋮ Finite state complexity ⋮ Deterministic Pushdown Automata and Unary Languages ⋮ Chrobak Normal Form Revisited, with Applications ⋮ 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

This page was built for publication: Simulating finite automata with context-free grammars.