# Greibach normal form

**Greibach normal form** (GNF) is a normal form for context-free grammars in which every production begins with a terminal symbol: each production has the form A → aα, where a is a terminal and α is a possibly empty string of variables. A common formulation allows a single exception, S → ε, when the empty string is in the language and the start symbol S appears on no right-hand side.<sup>[1](https://alphabetamath.cc/item/def-greibach-normal-form)</sup><sup> • </sup><sup>[2](https://www.munotes.in/notes/BSc-Computer-Science/SY-BSc-Computer-Science/Semester-3/Theory-of-Computation/greibach-normal-form/)</sup>

| Key fact | Detail |
|---|---|
| Production shape | A → aα with a a terminal and α a possibly empty string of variables; optional S → ε when ε is in the language and S occurs on no right-hand side<sup>[1](https://alphabetamath.cc/item/def-greibach-normal-form)</sup> |
| Coverage | Every context-free language is generated by a grammar in Greibach normal form<sup>[2](https://www.munotes.in/notes/BSc-Computer-Science/SY-BSc-Computer-Science/Semester-3/Theory-of-Computation/greibach-normal-form/)</sup> |
| Origin | Proven by Sheila Greibach, "A new normal-form theorem for context-free phrase structure grammars", *Journal of the ACM* 12(1):42–52, January 1965<sup>[3](https://projects.csail.mit.edu/jacm/Authors/greibachsheilaa.html)</sup> |
| Derivation length | A derivation of a string of length n takes exactly n steps; in Chomsky normal form it takes 2n − 1 steps<sup>[2](https://www.munotes.in/notes/BSc-Computer-Science/SY-BSc-Computer-Science/Semester-3/Theory-of-Computation/greibach-normal-form/)</sup> |
| Left recursion | Not permitted in GNF; it must be removed during conversion<sup>[2](https://www.munotes.in/notes/BSc-Computer-Science/SY-BSc-Computer-Science/Semester-3/Theory-of-Computation/greibach-normal-form/)</sup> |
| Main use | Constructing a pushdown automaton that simulates leftmost derivations of a context-free grammar<sup>[4](https://opendsa-server.cs.vt.edu/ODSA/Books/CS4114S22notes/html/PDACFL.html)</sup> |
| Conversion cost | The Hopcroft and Ullman algorithm is formally verified and can have exponential complexity, with blowup as bad as \( 2^{n^2} \) for n nonterminals<sup>[5](https://isa-afp.org/browser_info/current/AFP/Greibach_Normal_Form/Greibach_Normal_Form.html)</sup> |

## Definition and immediate consequences

A context-free grammar G = (V, Σ, P, S) is in Greibach normal form when every production in P is of the form A → aα, where A is a variable, a is a terminal, and α is a (possibly empty) string of variables. When the empty string belongs to the language, the formulation adds the single production S → ε, with S appearing on no right-hand side.<sup>[1](https://alphabetamath.cc/item/def-greibach-normal-form)</sup> Some textbook treatments restrict α further, for example to at most two variables, but the standard statement allows any number of variables, including none.<sup>[6](https://cs.wellesley.edu/~cs235/fall05/lectures/tr16.pdf)</sup>

Every derivation step emits exactly one terminal at its leftmost position, so a derivation of a string of length n takes exactly n steps. This contrasts with Chomsky normal form, where a production is either A → BC or A → a, and a derivation of a length-n string takes 2n − 1 steps, some producing no terminal at all.<sup>[2](https://www.munotes.in/notes/BSc-Computer-Science/SY-BSc-Computer-Science/Semester-3/Theory-of-Computation/greibach-normal-form/)</sup>

GNF sits differently from Chomsky normal form, so neither is a special case of the other. Chomsky normal form restricts the length of the right-hand side and places the terminal alone; Greibach normal form restricts the *positions* in which terminals and variables appear, allowing any number of variables after the leading terminal. GNF additionally rules out left recursion, while Chomsky normal form permits it.<sup>[2](https://www.munotes.in/notes/BSc-Computer-Science/SY-BSc-Computer-Science/Semester-3/Theory-of-Computation/greibach-normal-form/)</sup>

The form is also distinct from the stricter s-grammar (simple grammar): a GNF grammar may contain multiple rules sharing the same pair (A, a), while an s-grammar allows each such pair in at most one rule, so that parsing never needs to backtrack.<sup>[7](https://www.cs.sjsu.edu/~pollett/154.1.20s/Lec20200325.html)</sup><sup> • </sup><sup>[8](https://opendsa.cs.vt.edu/ODSA/Books/CS4114S22notes/html/CFLSimp.html)</sup>

## The normal-form theorem

The founding result is Sheila Greibach's theorem, published in the *Journal of the ACM* in January 1965 as "A new normal-form theorem for context-free phrase structure grammars"; Greibach was then at Harvard University.<sup>[3](https://projects.csail.mit.edu/jacm/Authors/greibachsheilaa.html)</sup><sup> • </sup><sup>[9](https://cir.nii.ac.jp/crid/1361418520582366592)</sup> The theorem states that every context-free grammar is equivalent to one in Greibach normal form; for languages containing the empty string, the equivalent GNF grammar generates the language minus ε, with the S → ε rule added separately.<sup>[2](https://www.munotes.in/notes/BSc-Computer-Science/SY-BSc-Computer-Science/Semester-3/Theory-of-Computation/greibach-normal-form/)</sup><sup> • </sup><sup>[10](https://www.cs.csustan.edu/~xliang/Courses2/CS4410-24F/NewLectureSlides/PDF/Ch06REC.pdf)</sup>

**Conversion algorithm.** The classical conversion, as presented by Hopcroft and Ullman, proceeds in stages:<sup>[11](https://www.iitg.ac.in/gkd/ma513/oct/oct18/note.pdf)</sup>

1. Eliminate null productions, unit productions, and useless symbols, and convert the grammar to Chomsky normal form for the language minus ε.
2. Rename the variables A1, A2, ..., An with S = A1, and modify the rules so that Ai → Ajγ implies j > i.
3. Working from A1 to An, substitute the bodies of earlier variables into later ones until each rule has the form Ak → Apγ with p ≥ k, then remove left recursion by introducing a new variable for each left-recursive variable.
4. Work back from An−1 down to A1, substituting so every right-hand side begins with a terminal.

Two substitution lemmas carry the proof. First, a production A → α1Bα2 can be replaced by A → α1β1α2, ..., A → α1βrα2, where B → β1 | ... | βr are all the B-productions, without changing the language. Second, left recursion A → Aα1 | ... | Aαr alongside A → β1 | ... | βs can be eliminated by adding a new variable Z with Z → αi | αiZ and replacing the A-productions by A → βi | βiZ.<sup>[11](https://www.iitg.ac.in/gkd/ma513/oct/oct18/note.pdf)</sup><sup> • </sup><sup>[12](https://www.cs.mun.ca/courses/cs4741/hopcroft-book.pdf)</sup> The Isabelle/HOL Archive of Formal Proofs formalizes this Hopcroft-Ullman algorithm and reports that the blowup can be as bad as \( 2^{n^2} \) for a starting grammar with n nonterminals and 4n productions; alternative polynomial methods exist in the literature.<sup>[5](https://isa-afp.org/browser_info/current/AFP/Greibach_Normal_Form/Greibach_Normal_Form.html)</sup> A 1986 Theoretical Computer Science paper gave a direct algorithm from any ε-free, chain-free context-free grammar to an equivalent GNF grammar.<sup>[13](https://www.sciencedirect.com/science/article/pii/0304397586901209)</sup>

## Why the form matters: pushdown automata

The central application of GNF is the proof that every context-free language is accepted by a nondeterministic pushdown automaton (PDA), a finite automaton with a stack.<sup>[4](https://opendsa-server.cs.vt.edu/ODSA/Books/CS4114S22notes/html/PDACFL.html)</sup><sup> • </sup><sup>[14](https://john.cs.olemiss.edu/~hcc/csci311/notes/chap07/ch07.html)</sup> Because every production of a GNF grammar begins with a terminal, a PDA can simulate leftmost derivations directly: for each production A → aX1X2...Xn, the automaton pops A from the stack, reads a from the input, and pushes X1X2...Xn. At any point in the derivation the sentential form consists of a terminal prefix matching the input read so far, followed by variables held on the stack.<sup>[4](https://opendsa-server.cs.vt.edu/ODSA/Books/CS4114S22notes/html/PDACFL.html)</sup><sup> • </sup><sup>[15](https://www-alg.ist.hokudai.ac.jp/~thomas/ToC/SLIDES/toc_lec10.pdf)</sup>

Nondeterminism resolves the choice among multiple productions with the same leading terminal, which is why the construction uses an NPDA rather than a deterministic machine. The construction underlies the classical equivalence of context-free grammars and pushdown automata.<sup>[4](https://opendsa-server.cs.vt.edu/ODSA/Books/CS4114S22notes/html/PDACFL.html)</sup>

## Relation to parsing practice

Beyond the PDA construction, GNF supplies a different bound on the time and space needed to parse a string generated by a context-free grammar, since each derivation step consumes one input symbol.<sup>[7](https://www.cs.sjsu.edu/~pollett/154.1.20s/Lec20200325.html)</sup> Left-recursive nonterminals cause top-down deterministic parsers to loop, and GNF provides a way of avoiding this problem, since every nonterminal in a GNF grammar is not left recursive.<sup>[16](https://www.cis.upenn.edu/~cis2620/notes/tcbook-u.pdf)</sup> Chomsky normal form serves the complementary purposes, underpinning the CYK parsing algorithm and the context-free pumping lemma.<sup>[2](https://www.munotes.in/notes/BSc-Computer-Science/SY-BSc-Computer-Science/Semester-3/Theory-of-Computation/greibach-normal-form/)</sup>

## Generalizations

The form has been carried into several broader settings. Moore and Crutchfield, in developing quantum automata and quantum grammars, found a Greibach normal form analog among the classical theorems they generalized, alongside pumping lemmas and closure properties.<sup>[17](https://arxiv.org/abs/quant-ph/9707031)</sup> Droste, Dziadek, and Kuich (2020) showed that mixed ω-algebraic systems, which describe weighted context-free languages of infinite words, can be transformed into Greibach normal form, and used this to prove that simple ω-reset pushdown automata recognize all ω-algebraic series; these automata use no ε-transitions and change the stack by at most one symbol per move.<sup>[18](https://arxiv.org/abs/2007.08866)</sup> For hypergraph grammars, Pshenitsyn (2020) introduced a weak Greibach normal form corresponding to the lexicalized normal form for string grammars and proved that every context-free hypergraph language, with nonsubstantial exceptions, can be generated by a grammar in this form.<sup>[19](https://arxiv.org/abs/2012.01660)</sup>

## References

1. [Greibach normal form, Alphabeta Math](https://alphabetamath.cc/item/def-greibach-normal-form)
2. [Greibach Normal Form notes, B.Sc. Computer Science Sem 3, munotes](https://www.munotes.in/notes/BSc-Computer-Science/SY-BSc-Computer-Science/Semester-3/Theory-of-Computation/greibach-normal-form/)
3. [Sheila A. Greibach publication list, MIT CSAIL JACM author pages](https://projects.csail.mit.edu/jacm/Authors/greibachsheilaa.html)
4. [Equivalence of NPDA and CFG, CS4114 Coursenotes, Virginia Tech](https://opendsa-server.cs.vt.edu/ODSA/Books/CS4114S22notes/html/PDACFL.html)
5. [Theory Greibach_Normal_Form, Archive of Formal Proofs](https://isa-afp.org/browser_info/current/AFP/Greibach_Normal_Form/Greibach_Normal_Form.html)
6. [Standardized tests: Chomsky and Greibach normal forms, CS235, Wellesley College](https://cs.wellesley.edu/~cs235/fall05/lectures/tr16.pdf)
7. [Chris Pollett, CS154 lecture of 25 March 2020, San Jose State University](https://www.cs.sjsu.edu/~pollett/154.1.20s/Lec20200325.html)
8. [Simplifying CFGs and Normal Forms, CS4114 Coursenotes, Virginia Tech](https://opendsa.cs.vt.edu/ODSA/Books/CS4114S22notes/html/CFLSimp.html)
9. [A New Normal-Form Theorem for Context-Free Phrase Structure Grammars, CiNii Research](https://cir.nii.ac.jp/crid/1361418520582366592)
10. [Automata, Computability, and Formal Language, lecture slides, CSUSTan](https://www.cs.csustan.edu/~xliang/Courses2/CS4410-24F/NewLectureSlides/PDF/Ch06REC.pdf)
11. [MA513 Formal Languages and Automata Theory, lecture notes, IIT Guwahati](https://www.iitg.ac.in/gkd/ma513/oct/oct18/note.pdf)
12. [Hopcroft and Ullman, section 4.3, Greibach Normal Form](https://www.cs.mun.ca/courses/cs4741/hopcroft-book.pdf)
13. [On Greibach normal form construction, Theoretical Computer Science](https://www.sciencedirect.com/science/article/pii/0304397586901209)
14. [CSci 311, Models of Computation, Chapter 7 Pushdown Automata, University of Mississippi](https://john.cs.olemiss.edu/~hcc/csci311/notes/chap07/ch07.html)
15. [Thomas Zeugmann, Theory of Computation, Lecture 10, Hokkaido University](https://www-alg.ist.hokudai.ac.jp/~thomas/ToC/SLIDES/toc_lec10.pdf)
16. [Jean Gallier, Introduction to the Theory of Computation, University of Pennsylvania](https://www.cis.upenn.edu/~cis2620/notes/tcbook-u.pdf)
17. [Cristopher Moore and James P. Crutchfield (1997), Quantum Automata and Quantum Grammars, arXiv](https://arxiv.org/abs/quant-ph/9707031)
18. [Manfred Droste, Sven Dziadek, Werner Kuich (2020), Greibach Normal Form for ω-Algebraic Systems and Weighted Simple ω-Pushdown Automata, arXiv](https://arxiv.org/abs/2007.08866)
19. [Tikhon Pshenitsyn (2020), Weak Greibach Normal Form for Hyperedge Replacement Grammars, arXiv](https://arxiv.org/abs/2012.01660)

---
*Topic: Encyclopedia › Society and history › Languages and linguistics › Linguistics › Formal and computational linguistics › Grammar normal forms and transformations*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 25, 2026 · Edited: Sep 30, 2026; Oct 11, 2026; Oct 25, 2026 · Last review: Oct 25, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license