Greibach normal form is a restricted shape for context-free grammars, one of several normal forms used in formal languages and the Chomsky hierarchy. Converting a grammar into it takes a sequence of small, mechanical steps, and the worked example below follows all of them on a two-variable grammar.
What is Greibach normal form?
Greibach normal form, usually shortened to GNF, restricts every rule of a context-free grammar to the shape A → aA1A2…An. The right-hand side starts with one terminal symbol a and continues with a sequence of nonterminals, which may be empty. A rule such as A → a is therefore perfectly valid, and so is A → aBC.
The form is meant for proofs and for parsing and automaton constructions that benefit from a grammar in which every rule starts by reading input. It is not a style for writing grammars by hand, because the conversion makes a grammar longer and harder to read. The result generates the same language as the original, but the rules look different and so do the parse trees.
The theorem behind the form is attributed to Greibach, who published it in the Journal of the ACM in 1965. In its usual statement it applies to context-free languages that do not contain the empty string.
What are the rules of a Greibach normal form grammar?
Each rule has the shape A → aw, where a is a terminal and w is a string of nonterminals, possibly empty. A → aBC fits as well, while a rule such as A → B0 does not, because it starts with a nonterminal and puts a terminal after it.
The empty string needs an agreement, and sources differ. The strict form generates no empty string at all and so describes only languages without it. The non-strict form allows one exception, the rule S → ε for the start symbol, which is permitted only when the empty string belongs to the language and S does not occur on the right-hand side of any rule. This page uses the non-strict form.
One property follows directly from the shape. A leftmost derivation of a nonempty string of length n takes exactly n steps in GNF, because every step produces exactly one terminal. A grammar in GNF also contains no left recursion, since no rule begins with a nonterminal.
How do you convert a context-free grammar to Greibach normal form?
The procedure follows a course page from the University of Maryland, Baltimore County, and a second page from the same department that states the preparatory steps. It has two phases.
- Prepare the grammar: remove useless symbols, then empty rules, then unit rules, and bring it into Chomsky normal form, where each rule is either A → BC or A → a.
- Number the variables A1 to Am in a fixed order.
- Work through the variables in that order. If a rule for Ai begins with Aj and j is smaller than i, replace Aj by each of its alternatives. Repeat until every rule of Ai begins with a terminal or with Aj where j is at least i.
- If a rule Ai → Aiα remains, which is direct left recursion, add a fresh variable B and rewrite the rules so that the recursion moves to the right.
- Substitute backward, from Am down to A1, so that every leading variable is replaced by alternatives that start with a terminal. Do the same for the fresh variables.
Courses order the preparatory steps differently; some begin with a new start symbol, others with useless symbols. This page uses the order from the Maryland pages.
Worked example: S → AA | 0, A → SS | 1
The starting grammar has two variables and four rules:
S → AA | 0
A → SS | 1 Step 1. The grammar is already in Chomsky normal form: each rule is either two nonterminals or a single terminal.
Step 2. Rename S to A1 and A to A2:
A1 → A2 A2 | 0
A2 → A1 A1 | 1 Step 3. Check the rules against the order. A1 → A2A2 is fine, since 2 is larger than 1. A2 → A1A1 breaks the order, because it begins with a variable of lower number.
Step 4. Replace the leading A1 in that rule by both of its alternatives:
A2 → A2 A2 A1 | 0 A1 | 1 Step 5. The rule A2 → A2A2A1 is left recursive. A fresh variable B takes over the repeating part:
A2 → 1 | 0 A1 | 1 B | 0 A1 B
B → A2 A1 | A2 A1 B Step 6. Now the rules of A1 are processed, substituting the four alternatives of A2 for the leading variable:
A1 → 1 A2 | 0 A1 A2 | 1 B A2 | 0 A1 B A2 | 0 Step 7. The rules of B begin with A2 as well, so each of its two rules turns into four, eight in total:
B → 1 A1 | 0 A1 A1 | 1 B A1 | 0 A1 B A1
| 1 A1 B | 0 A1 A1 B | 1 B A1 B | 0 A1 B A1 B Step 8. The result has three variables and seventeen rules: five for A1, four for A2 and eight for B. Every right-hand side starts with a terminal and continues with nonterminals only. Listing every string up to length 12 from both grammars gives the same 2,725 strings. Such a comparison finds mistakes but does not prove equivalence; that rests on the procedure itself.
Why must left recursion be removed first?
A left-recursive rule begins with a nonterminal that leads back to itself, as in A → Aα. Substitution cannot turn such a rule into one that starts with a terminal, because each substitution brings back the same leading variable, so the rule has to be rewritten first.
For direct left recursion, the alternatives that do not begin with A supply the new starting points, and the repeating tails go into a fresh variable. The recursion then runs on the right, where it does no harm to the shape of the rules. Indirect left recursion, in which A leads to B and B leads back to A, disappears in the ordering step, because substituting earlier variables before the current one removes the cycle.
What is the difference between CNF and GNF?
Chomsky normal form limits the length of right-hand sides, and Greibach normal form limits what they start with.
| Property | Chomsky normal form | Greibach normal form |
|---|---|---|
| Rule shape | A → BC or A → a | A → aw, w a string of nonterminals |
| Terminals consumed per leftmost step | zero or one | exactly one |
| Left recursion | possible | not possible |
| Example grammar above | 4 rules | 17 rules |
Chomsky normal form is also the starting point of the conversion described above.
Why is Greibach normal form useful, and what does it cost?
Its main benefit is that every derivation step consumes one terminal, so the number of steps for a string equals its length. Because of this, a top-down parser working from a GNF grammar halts at a depth no larger than the length of the input.
The price is size and clarity. In the example, four rules became seventeen, and the original structure is no longer visible. Published size bounds exist for specific constructions, but they belong to the algorithm that was analyzed, so one worked example says little about growth in general. When diagnostics refer back to the grammar an author wrote, a record of which new rule came from which old one is worth keeping.
How do you check a converted grammar?
First, inspect the syntax: every rule must begin with exactly one terminal, and everything after it must be a nonterminal.
Second, compare behavior. Generate all strings of the original and the converted grammar up to a chosen length and compare the two sets. The comparison exposes lost or invented strings but cannot show equivalence beyond the chosen length. Last, decide the empty string on purpose: either the language lacks it, or the special rule S → ε is present and S appears on no right-hand side.
Frequently asked questions
01What is the difference between CNF and GNF?
Chomsky normal form allows only two kinds of rule, A → BC and A → a. Greibach normal form requires every rule to start with a terminal followed by any number of nonterminals, A → aw. A grammar in one form is usually not in the other, and the conversion between them changes the number of rules.
02Can every context-free grammar be converted to Greibach normal form?
Every context-free language that does not contain the empty string has a grammar in Greibach normal form. If the language does contain the empty string, the common definition adds the single rule S → ε, with S kept off all right-hand sides. Without that exception the empty string cannot be produced.
03Can the start symbol produce epsilon in GNF?
In the non-strict form, yes: S → ε is allowed when the language contains the empty string, as long as S does not appear on any right-hand side. The strict form allows no such rule, so it only describes languages without the empty string.
04How do I verify a converted GNF grammar?
Check that every rule begins with one terminal followed only by nonterminals, then compare the strings both grammars generate up to a chosen length. A match up to that length catches mistakes but does not prove the two grammars equivalent. Treat the empty string separately.