A new algorithm for regularizing one-letter context-free grammars.

DOI10.1016/S0304-3975(03)00215-9zbMath1059.68052MaRDI QIDQ1426442

Ştefan Andrei, Wei-Ngan Chin, Salvador Valerio Cavadini

Publication date: 14 March 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

One-letter context-free languageReduction of a context-free grammarRegular expression

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Theory of compilers and interpreters (68N20) Grammars and rewriting systems (68Q42)

Related Items

Selected Topics in Computational Complexity of Membrane Systems, Non-Self-Embedding Grammars and Descriptional Complexity, ON THE POWER OF FAMILIES OF RECOGNIZER SPIKING NEURAL P SYSTEMS

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Infinite linear systems and one counter languages
• Finite automata and unary languages
• Two iteration theorems for some families of languages
• Language equations over a one-letter alphabet with union, concatenation and star: A complete solution
• Simulating finite automata with context-free grammars.
• On certain formal properties of grammars
• On Context-Free Languages
• Two Families of Languages Related to ALGOL