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

DOI10.1016/S0304-3975(03)00215-9MaRDI QIDQ1426442zbMATH OpenFDO

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

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)

Recommendations

• A REGULARITY CONDITION FOR CONTEXT-FREE GRAMMARS
• A new one pass algorithm for estimating stochastic context-free grammars
• scientific article; zbMATH DE number 39880
• Strongly Regular Grammars and Regular Approximation of Context-Free Languages
• A new regular grammar pattern matching algorithm.
• Regular approximation of context-free grammars through transformation
• Results of NLC grammars with one-letter terminal alphabets
• A new regular grammar pattern matching algorithm
• An extension of context-free grammars with one-sided context specifications

Cites work

• scientific article; zbMATH DE number 3174044 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• scientific article; zbMATH DE number 3307592 (Why is no real title available?)
• Finite automata and unary languages
• Infinite linear systems and one counter languages
• Language equations over a one-letter alphabet with union, concatenation and star: A complete solution
• On Context-Free Languages
• On certain formal properties of grammars
• On the decomposition of finite languages
• Simulating finite automata with context-free grammars.
• Two Families of Languages Related to ALGOL
• Two iteration theorems for some families of languages

Cited in

(7)

• Regular approximation of context-free grammars through transformation
• Non-self-embedding grammars and descriptional complexity
• Strongly Regular Grammars and Regular Approximation of Context-Free Languages
• scientific article; zbMATH DE number 39880 (Why is no real title available?)
• On the power of families of recognizer spiking neural P systems
• Regular approximation of CFLs: A grammatical view
• Selected Topics in Computational Complexity of Membrane Systems

Describes a project that uses

Uses Software

• ALGOL 60

This page was built for publication: A new algorithm for regularizing one-letter context-free grammars.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1426442)