Greibach Normal Form (GNF)

Introduction

GNF (Greibach Normal Form) is a specialized form of Context-Free Grammar (CFG) where each production rule begins with a terminal symbol, followed by optional variables.

A CFG (Context-Free Grammar) is a Greibach Normal Form(GNF) if all of its production rules satisfy one of the following conditions:

1. A non-terminal generating terminal. For example,  B -> b.
2. Start symbol generating ε. For example, S → ε.
3. A non-terminal generates a terminal followed by any number of non-terminals. For example, A -> aBC…N.

Also read about - Chomsky Hierarchy

For example:

G1 = {S → aAB | bBA, A → aA | a, B → bB | b}  
G2 = {S → aAB | aBA, A → aA | ε, B → bB | ε}  

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

Also read,  Arden's theorem

Notes:

1. There can be more than one GNF for a given grammar.
2. GNF produces the same language as CFG produces.
    

Also see, Turing Machine in TOC.

Steps for Converting CFG into GNF

Step 1 - Convert the Grammar into Chomsky Normal Form(CNF): If the given Grammar is not in CNF, convert it.

Step 2 - If the grammar contains left recursion, remove it. 

Step 3 - Convert the production rule into GNF form in the grammar. 

Read About - Simplification of CFG

Let’s understand with an example,

Question: Consider the following Grammar G. Convert it into GNF.

S → AA | BC 
A → a|SA 
B → a
C → c

Solution: 

We can skip steps 1 and 2 and move directly to step 3 because the given grammar G is already in CNF, and there is no left recursion.

1. The production rule A → SA is not in GNF, so we substitute S -> AA | BC in the production rule A → SA as

S → AA | BC 
A → a | AAA | BCA 
B → a
C → c

2. The production rule S → BC and A → BCA is not in GNF, so we substitute B → a in the production rule S → BC and A → BCA as

S → AA | aC 
A → a | AAA | aCA 
B → a
C → c

3. Next, we will remove the left recursion (A → AAA), we get

S → AA | aC 
A → aX | aCAX
X → AAX | ε  
B → a
C → c

4. Now remove the null production X → ε, we get

S → AA | aC 
A → aX | aCAX | a | aCA
X → AAX | AA
B → a
C → c

5. Now, S → AA  and X → AA are not in GNF, so we substitute A → aX | aCAX | a | aCA in production rule S → AA and X → AA as

S → aXA | aCAXA | aA | aCAA | aC 
A → aX | aCAX | a | aCA
X → AAX 
X → aXA | aCAXA | aA | aCAA
B → a
C → c

6. Lastly, X → AAX is not in GNF,  so we substitute A → aX | aCAX | a | aCA in production rule X → AAX as

S → aXA | aCAXA | aA | aCAA | aC 
A → aX | aCAX | a | aCA
X → aXAX | aCAXAX | aAX | aCAAX
X → aXA | aCAXA | aA | aCAA
B → a
C → c

Hence, it is the GNF of Grammar G, as all the production rules follow one of the rules mentioned above.

Also read - Theory of Computation