1 of 6

Session 9: �Greibach Normal form (GNF)

By

Dr. Ashok Kumar

Amity School of Engineering & Technology

2 of 6

Greinbach Normal Form

2

All productions have form:

symbol

variables

Amity School of Engineering & Technology

3 of 6

Conversion from CFG to GNF

A CFG(context free grammar) is in GNF(Greibach normal form) if all the production rules satisfy one of the following conditions:

​

  • A start symbol generating ε. For example, S → ε.
  • A non-terminal generating a terminal. For example, A → a.
  • A non-terminal generating a terminal which is followed by any number of non-terminals. For example, S → aASB.

For example:

G1 = {S → aAB | aB, A → aA| a, B → bB | b}

G2 = {S → aAB | aB, A → aA | ε, B → bB | ε}

The production rules of Grammar G1 satisfy the rules specified for GNF, so the grammar G1 is in GNF. However, the production rule of Grammar G2 does not satisfy the rules specified for GNF as A → ε and B → ε contains ε(only start symbol can generate ε). So the grammar G2 is not in GNF.

Amity School of Engineering & Technology

4 of 6

4

Examples:

Greinbach

Normal Form

Not Greinbach

Normal Form

Amity School of Engineering & Technology

5 of 6

5

Greinbach

Normal Form

Amity School of Engineering & Technology

6 of 6

6

Observations

  • Greinbach normal forms are very good

for parsing

  • It is hard to find the Greinbach normal

form of any context-free grammar

Amity School of Engineering & Technology