On Greibach normal form construction

DOI10.1016/0304-3975(85)90173-2MaRDI QIDQ5903291zbMATH OpenOpenAlexFDO

Authors Friedrich J. Urbanek

Publication date 1985

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

Full work available at URL https://doi.org/10.1016/0304-3975(85)90173-2

zbMATH Keywords

Chomsky normal formcontext-free grammarGreibach normal formpure derivation-oriented reasoning

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

In this note we present a procedure to rewrite a given Chomsky normal form grammar in Greibach normal form. This procedure yields the same grammar as the well-known procedure of Rosenkrantz, but is based on pure derivation-oriented reasoning and not on systems of equations.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Matrix Equations and Normal Forms for Context-Free Grammars

Cited in

(12)

• Über die Konstruktion der Jordanschen Normalform. (On the construction of the Jordan normal form)
• An elementary proof of double Greibach normal form
• Context-free graph languages of bounded degree are generated by apex graph grammars
• Double Greibach operator grammars
• Greibach normal form transformation revisited.
• Language equivalence of probabilistic pushdown automata
• Extended goursat normal form: a geometric characterization
• scientific article; zbMATH DE number 4079959 (Why is no real title available?)
• A formalization of Sambins's normalization for GL
• An Optimal Gaifman Normal Form Construction for Structures of Bounded Degree
• On Greibach normal form construction
• An elementary proof of a generalization of double Greibach normal form

This page was built for publication: On Greibach normal form construction

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