An elementary proof of double Greibach normal form

DOI10.1016/0020-0190(92)90101-ZMaRDI QIDQ1209361zbMATH OpenOpenAlexFDO

Authors Joost Engelfriet

Publication date 16 May 1993

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

Full work available at URL https://doi.org/10.1016/0020-0190(92)90101-z

zbMATH Keywords

context-free grammarsGreibach normal form

Mathematics Subject Classification ID

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

Recommendations

• An easy proof of Greibach normal form
• On Greibach normal form construction
• Greibach normal form transformation revisited.
• On Greibach normal form construction
• Greibach normal form transformation, revisited

Cites work

• A Greibach normal form for context-free graph grammars
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• An easy proof of Greibach normal form
• Context-free graph languages of bounded degree are generated by apex graph grammars
• Matrix Equations and Normal Forms for Context-Free Grammars
• On Greibach normal form construction
• On Greibach normal form construction

Cited in

(9)

• Double Greibach operator grammars
• A pumping lemma for flip-pushdown languages
• On Greibach normal form construction
• An elementary proof of a generalization of double Greibach normal form
• Limited automata and unary languages
• An easy proof of Greibach normal form
• Non-erasing Chomsky-Schützenberger theorem with grammar-independent alphabet
• Identification in the Limit of k,l-Substitutable Context-Free Languages
• Quasi-rocking real-time pushdown automata

This page was built for publication: An elementary proof of double Greibach normal form

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