Encyclopedia

Greibach normal form

Form for context-free grammars

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated July 19, 2026

In formal language theory, a context-free grammar is in Greibach normal form (GNF) if the right-hand sides of all production rules start with a terminal symbol, optionally followed by some non-terminals. A non-strict form allows one exception to this format restriction for allowing the empty word (epsilon, ε) to be a member of the described language. The normal form was established by Sheila Greibach and it bears her name.

More precisely, a context-free grammar is in Greibach normal form, if all production rules are of the form:

$A\to aA_{1}A_{2}\cdots A_{n}$

where $A$ is a nonterminal symbol, $a$ is a terminal symbol, and $A_{1}A_{2}\ldots A_{n}$ is a (possibly empty) sequence of nonterminal symbols.

Observe that the grammar does not have left recursions.

Every context-free grammar can be transformed into an equivalent grammar in Greibach normal form. Various constructions exist. Some do not permit the second form of rule and cannot transform context-free grammars that can generate the empty word. For one such construction the size of the constructed grammar is O(n⁴) in the general case and O(n³) if no derivation of the original grammar consists of a single nonterminal symbol, where n is the size of the original grammar. This conversion can be used to prove that every context-free language can be accepted by a real-time (non-deterministic) pushdown automaton, i.e., the automaton reads a letter from its input every step.

Given a grammar in GNF and a derivable string in the grammar with length n, any top-down parser will halt at depth n.

01Variants of Greibach normal form

It is even possible to convert a grammar into Greibach normal form in a way such that in every production, at most two nonterminal symbols occur on the right-hand side; this is referred to as quadratic Greibach normal form.

A context-free grammar is in double Greibach normal form, if all production rules take one of the two forms:

$A\to aA_{1}A_{2}\cdots A_{n}b$

$A\to a$

where $A$ is a nonterminal symbol, $a,b$ are terminal symbols (not necessarily distinct), and $A_{1}A_{2}\ldots A_{n}$ is a (possibly empty) sequence of nonterminal symbols. Similarly as above, a grammar is in quadratic double Greibach normal form, if at most two nonterminal symbols occur in the right-hand side of each production. A classic result by Hotz (1978) states that every context-free grammar that does not generate the empty word can be effectively converted into an equivalent grammar in quadratic double Greibach normal form.

Watch videos about Greibach normal formExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Greibach normal form”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Greibach normal form

01Variants of Greibach normal form

Sources and credits

Related topics

Backus-Naur form

Chomsky normal form

Kuroda normal form