Chapter 21 of 34

Greibach Normal Form

In Chomsky Normal Form every production has a very rigid shape: two variables, or one terminal. That shape is perfect for algorithms such as CYK, but it says nothing about when terminals appear during a derivation. A CNF derivation can expand variables for a long time before producing a single symbol of the output.

Greibach Normal Form (GNF), introduced by Sheila Greibach in 1965, takes the opposite view: every production must start with a terminal. So every step of a derivation emits exactly one symbol of the final string, from left to right. This makes GNF the natural bridge between grammars and pushdown automata, and it guarantees there is no left recursion.

A context-free grammar is in Greibach Normal Form if every production has the form A → aα, where a is a terminal and α is a (possibly empty) string of variables. If ε is in the language, the single extra production S → ε is allowed, provided the start symbol S does not appear on the right side of any production.

In this chapter we will see why GNF is useful, learn the two tools used to reach it (substitution and removal of left recursion), and convert three grammars step by step. Every converted grammar in this chapter was produced by a program and then checked to generate exactly the same strings as the original, for all strings up to length 10 or more.


What GNF Looks Like

Read A → aα as: "to expand A, first write the terminal a, then leave behind the variables α to be expanded later". Some valid and invalid productions:

Production

In GNF?

Reason

A → a

Yes

α is empty, which is allowed

A → bBC

Yes

One terminal followed by variables only

S → ε

Only for the start symbol

And only if S never appears on a right side

A → BC

No

Starts with a variable (this is CNF shape)

A → aBb

No

A terminal appears after the first position

A → ab

No

Same problem: b must be replaced by a variable B with B → b

A → Aa

No

Starts with a variable (left recursive)

Theorem (Greibach, 1965): every context-free language L with ε ∉ L is generated by some grammar in GNF. If ε ∈ L, add S → ε as described above.


Why GNF Is Useful

  • One terminal per step. Each production adds exactly one terminal, so a string of length n ≥ 1 is derived in exactly n steps. Compare CNF, where a string of length n ≥ 1 takes exactly 2n − 1 steps (n − 1 steps of the form A → BC and n steps of the form A → a).

  • No left recursion. Since every right side begins with a terminal, a leftmost derivation can never loop on A ⇒ A… without making progress. This is why GNF matters for top-down parsing.

  • Direct PDA construction. For A → aα the PDA can read a and replace A on the stack by α in a single move, with no ε-moves at all (apart from S → ε). This is used in Equivalence of PDA & CFG.

  • Proofs. Many results about CFLs become easier to prove when every derivation step is tied to one input symbol.


The Two Tools

Converting to GNF uses only two transformations, and each one keeps the language unchanged.

Tool 1: Substitution

If A → Bγ is a production and B → β1 | β2 | … | βr are all the B-productions, then A → Bγ can be replaced by A → β1γ | β2γ | … | βrγ.

Why it is safe: any derivation that used A → Bγ had to expand that B with one of its productions sooner or later. We are simply doing that expansion in advance.

Tool 2: Removing (Immediate) Left Recursion

Suppose the A-productions are

A → Aα1 | Aα2 | … | Aαr        (left recursive)
A → β1  | β2  | … | βs         (do not start with A)

Any string derived from A looks like one β followed by any number of α's: A ⇒* βi αj1 αj2 … . We can generate the same thing "from the left" using a new variable Z that produces one or more α's:

A → β1 | β2 | … | βs | β1 Z | β2 Z | … | βs Z
Z → α1 | α2 | … | αr | α1 Z | α2 Z | … | αr Z

For example, A → Aa | b generates b, ba, baa, … . The new rules A → b | bZ and Z → a | aZ generate exactly the same strings, with no left recursion. (Some books write A → β | βZ and Z → α | αZ with ε-free Z, as here; others use Z → αZ | ε. In GNF conversion we use the ε-free version, because GNF does not allow ε-productions.)


Example 1: Substitution Is Enough

S → AB
A → aA | bB | b
B → b

A and B are already in GNF. Only S → AB starts with a variable. Substitute the three A-productions:

S → aAB | bBB | bB
A → aA | bB | b
B → b

Every production now starts with a terminal followed only by variables. Done. Both grammars generate the strings anbb and anbbb for n ≥ 0 (bb, bbb, abb, abbb, aabb, …).


Example 2: Left Recursion and Stray Terminals

S → Sab | b

This generates b, bab, babab, … , i.e. b(ab)*.

Step 1: remove the left recursion. Here α = ab and β = b:

S → b | bZ
Z → ab | abZ

Step 2: the second b in Z → ab is a terminal in a non-first position. Introduce B → b and use it:

S → b | bZ
Z → aB | aBZ
B → b

This is in GNF. Check one derivation of "babab" (length 5):

S ⇒ bZ ⇒ baBZ ⇒ babZ ⇒ babaB ⇒ babab        (exactly 5 steps)

Each step produced one new terminal, as promised. A program confirmed that both grammars generate exactly b(ab)* for all strings up to length 11.


The General Algorithm

Examples 1 and 2 were easy because the variables did not refer back to each other. In general, A may start with B, B with C, and C with A again (indirect left recursion). The standard algorithm (as in Hopcroft and Ullman) handles this by ordering the variables.

Input: a grammar in CNF without ε-productions (see "Chomsky Normal Form").

Step 1. Rename the variables A1, A2, …, Am (A1 = start symbol).

Step 2. Make every production of the form  Ai → Aj γ  satisfy  j > i.
        for k = 1 to m:
            while some production Ak → Aj γ has j < k:
                substitute the Aj-productions into it        (Tool 1)
            if some productions are Ak → Ak α:
                remove the left recursion with a new variable Zk   (Tool 2)
        Now every Ak-production starts with a terminal or with Aj, j > k.

Step 3. Back-substitution.
        Am-productions all start with a terminal (there is no higher variable).
        for k = m−1 down to 1:
            substitute into each Ak → Aj γ  (j > k; Aj is already in GNF)

Step 4. Each Zk-production starts with some Ai; substitute the
        (now GNF) Ai-productions.

Step 5. If any terminal appears in a non-first position, replace it
        by a new variable (B → b).

Why does Step 2 terminate? When we substitute into Ak → Ajγ with j < k, the Aj-productions already start with a terminal or with Al where l > j. So the leading index strictly increases with every substitution, until it reaches k (left recursion, removed by Tool 2) or goes above k.


Example 3: A Full Conversion

This is the classic textbook grammar, already in CNF, with variables already numbered:

A1 → A2 A3
A2 → A3 A1 | b
A3 → A1 A2 | a

Step 2, k = 1 and k = 2

A1 → A2A3: leading index 2 > 1, fine.

A2 → A3A1: 3 > 2, fine. A2 → b starts with a terminal, fine.

Step 2, k = 3

A3 → A1A2 has 1 < 3. Substitute A1 → A2A3:

A3 → A2 A3 A2 | a

Still 2 < 3. Substitute A2 → A3A1 | b:

A3 → A3 A1 A3 A2 | b A3 A2 | a

Now A3 is left recursive with α = A1A3A2, and β1 = bA3A2, β2 = a. Apply Tool 2 with a new variable Z3:

A3 → b A3 A2 | a | b A3 A2 Z3 | a Z3
Z3 → A1 A3 A2 | A1 A3 A2 Z3

The grammar now is:

A1 → A2 A3
A2 → A3 A1 | b
A3 → bA3A2 | a | bA3A2Z3 | aZ3          ← already GNF
Z3 → A1A3A2 | A1A3A2Z3

Step 3: back-substitution

A2: substitute the four A3-productions into A2 → A3A1, keep A2 → b:

A2 → bA3A2A1 | aA1 | bA3A2Z3A1 | aZ3A1 | b

A1: substitute the five A2-productions into A1 → A2A3:

A1 → bA3A2A1A3 | aA1A3 | bA3A2Z3A1A3 | aZ3A1A3 | bA3

Step 4: fix Z3

Both Z3-productions start with A1, which has 5 productions, so we get 2 × 5 = 10 productions:

Z3 → bA3A2A1A3A3A2 | aA1A3A3A2 | bA3A2Z3A1A3A3A2 | aZ3A1A3A3A2 | bA3A3A2
   | bA3A2A1A3A3A2Z3 | aA1A3A3A2Z3 | bA3A2Z3A1A3A3A2Z3 | aZ3A1A3A3A2Z3 | bA3A3A2Z3

Final GNF grammar

Variable

Productions

Count

A1

bA3A2A1A3 | aA1A3 | bA3A2Z3A1A3 | aZ3A1A3 | bA3

5

A2

bA3A2A1 | aA1 | bA3A2Z3A1 | aZ3A1 | b

5

A3

bA3A2 | a | bA3A2Z3 | aZ3

4

Z3

the 10 productions listed in Step 4

10

Total

24

No terminal appears in a non-first position, so Step 5 is not needed. The original grammar had 5 productions; the GNF one has 24. Such growth is typical: GNF conversion can make a grammar much larger.

Checking the result. The shortest strings generated by A1 are ba, abaa, bbab. With the GNF grammar:

A1 ⇒ bA3 ⇒ ba                                   (2 symbols, 2 steps)
A1 ⇒ aA1A3 ⇒ abA3A3 ⇒ abaA3 ⇒ abaa              (4 symbols, 4 steps)

And in the original grammar: A1 ⇒ A2A3 ⇒ bA3 ⇒ ba, which takes 3 = 2·2 − 1 steps, as expected for CNF. A program compared the two grammars on all 2047 strings over {a, b} of length ≤ 10: both generate exactly the same 151 strings.


GNF vs CNF

Aspect

Chomsky Normal Form

Greibach Normal Form

Production shape

A → BC or A → a

A → aα, α ∈ V*

Right side length

1 or 2

Any length ≥ 1

Steps to derive a string of length n ≥ 1

2n − 1

n

Parse tree shape

Binary tree

Each internal node's leftmost child is a terminal

Left recursion

Possible

Impossible

Main use

CYK algorithm, pumping lemma proof

ε-free PDA construction, top-down parsing theory

Conversion effort

Easy, small growth

Harder, can blow up the grammar

A stronger result also holds: every ε-free CFL has a GNF grammar in which every right side has at most two variables after the terminal (A → a, A → aB or A → aBC). This is sometimes called quadratic GNF. You will rarely need it in exams, but it shows that GNF does not require long right sides.


Common Mistakes

  • Leaving terminals inside α. A → aBb is not GNF. Replace the trailing b by a variable B' with B' → b.

  • Starting without cleaning the grammar. Remove ε-productions, unit productions and useless symbols first (see Simplification of CFGs). Unit productions such as A → B break the "leading index increases" argument.

  • Substituting in the wrong order. In Step 2 go upwards (k = 1, 2, …); in Step 3 go downwards (k = m − 1, …, 1). Back-substitution only works because the higher variables are finished first.

  • Forgetting to substitute into the new Z variables. Z-productions begin with original variables, so they need Step 4.

  • Using Z → αZ | ε. That reintroduces ε-productions. Use the ε-free form A → β | βZ, Z → α | αZ.

  • Thinking GNF changes the language. It only changes the grammar. The only special care is ε, which needs the separate S → ε rule.


Practice and GATE-Style Questions

Q1. A grammar G is in GNF and has no ε-production. How many steps does a derivation of a string of length 12 take? What if G were in CNF?

GNF: each step emits exactly one terminal, so 12 steps. CNF: 2 × 12 − 1 = 23 steps (11 binary steps that create 12 variable leaves, then 12 terminal steps).

Q2. Which of these productions are in GNF? (i) S → aSB (ii) S → aSb (iii) A → B (iv) A → c (v) B → bAAAA

(i), (iv) and (v) are in GNF. (ii) has a terminal b after the first position. (iii) is a unit production starting with a variable.

Q3. Convert A → Ac | Ad | e | f to a form without left recursion suitable for GNF.

Here α1 = c, α2 = d, β1 = e, β2 = f:

A → e | f | eZ | fZ
Z → c | d | cZ | dZ

All productions already start with a terminal followed only by variables, so this is in GNF. Both grammars generate (e + f)(c + d)*.

Q4. Convert to GNF: S → AA | a, A → SS | b.

Number S = A1, A = A2. A1 → A2A2 | a is fine (2 > 1). For A2 → A1A1, substitute A1: A2 → A2A2A1 | aA1 | b. Remove left recursion (α = A2A1, β = aA1, b):

A2 → aA1 | b | aA1Z | bZ
Z  → A2A1 | A2A1Z

Back-substitute into A1 → A2A2 and into Z:

A1 → aA1A2 | bA2 | aA1ZA2 | bZA2 | a
A2 → aA1 | b | aA1Z | bZ
Z  → aA1A1 | bA1 | aA1ZA1 | bZA1 | aA1A1Z | bA1Z | aA1ZA1Z | bZA1Z

A program confirmed that this grammar and the original generate the same strings up to length 10.

Q5. Interview: why can a GNF grammar never be left recursive, and why does that matter?

Every right side starts with a terminal, so in a leftmost derivation each step fixes one more input symbol. A ⇒+ Aγ would require deriving a sentential form that starts with a variable, which is impossible. For a top-down (recursive-descent) parser this means it can never loop forever without consuming input; for a PDA it means every move reads one input symbol, so the PDA needs no ε-moves.


Summary

  • GNF: every production is A → aα with a a terminal and α a string of variables (S → ε allowed in the special case).

  • Every ε-free CFL has a GNF grammar (Greibach's theorem).

  • Each derivation step emits one terminal: n steps for a string of length n (CNF needs 2n − 1).

  • Tools: substitution (A → Bγ becomes A → βγ) and left-recursion removal (A → Aα | β becomes A → β | βZ, Z → α | αZ).

  • General algorithm: number the variables, make leading indexes increase, remove left recursion, back-substitute from Am down to A1, fix the Z variables, then replace stray terminals.

  • GNF grammars have no left recursion and lead directly to ε-move-free PDAs.

In GNF every step writes one symbol: first the terminal, then the variables still to be expanded. Get there by substituting forward, removing left recursion, and substituting back.