Double Greibach operator grammars
From MaRDI portal
Every context-free grammar can be transformed into one in double Greibach operator form, that satisfies both double Greibach form and operator form. Examination of the expressive power of various well-known subclasses of context-free grammars in double Greibach and/or operator form yields an extended hierarchy of language classes. Basic decision properties such as equivalence can be stated in stronger forms via new classes of languages in this hierarchy.
Recommendations
Cites work
- A hierarchy of eNCE families of graph languages
- A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
- An elementary proof of double Greibach normal form
- Apex graph grammars and attribute grammars
- Boundary graph grammars with dynamic edge relabeling
- Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
- Context-free graph languages of bounded degree are generated by apex graph grammars
- Efficient recognition algorithms for boundary and linear eNCE graph languages
- Handle-rewriting hypergraph grammars
- HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting
- scientific article; zbMATH DE number 3639163 (Why is no real title available?)
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- scientific article; zbMATH DE number 3413820 (Why is no real title available?)
- Linear graph grammars: Power and complexity
- Matrix Equations and Normal Forms for Context-Free Grammars
- Node replacement graph languages squeezed with chains, trees, and forests
- On Equivalence and Containment Problems for Formal Languages
- On Greibach normal form construction
- Separating \(k\)-separated eNCE graph languages
- Syntactic Analysis and Operator Precedence
Cited in
(2)
This page was built for publication: Double Greibach operator grammars
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1589438)
