S => ABA | AB | BA | AA | A | B - A => aA | b - B => bB | b -

• A CFG G = (V, T, R, S) is said to be in GNF if every production is of the form

  A → aα, where a ∈ T and α ∈ V∗

  i.e., α is a string of zero or more variables.

• Definition: A production U ∈ R is said to be in the form left recursion, if U : A → Aα for some A ∈ V .

• Left recursion in R can be eliminated by the following scheme:

  a.) If A → Aα1| Aα2 | . . . | Aαr | β1 | β2 | . . . | βs, then replace the above rules by

  • Z → αi | αiZ, 1 ≤ i ≤ r

  • A → βi | βiZ, 1 ≤ i ≤ s

  b.) If G = (V, T, R, S) is a CFG, then we can construct another CFG G1 = (V1, T, R1,S) in Greibach Normal Form (GNF) such that L(G1) = L(G) − {є}

Steps to convert a CFG to GNF

Step1: Rename variables

Let S be $A_1$, A be $A_2$, B be $A_3$

The grammar now becomes

$A_1 =\gt A_1A_2A_3 \ | \ A_2A_3 \ | \ A_3A_3 \ | \ A_2A_2 \ | \ A_2 \ | \ A_3$

$A_2 =\gt aA_2 \ | \ a$

$A_3 =\gt bA_3 \ | \ b$

Step 2: For each $A_i =\gt A_j$, ensure i <= j, which is satisfied in all cases

Step 3: Remove left recursion, which is not seen in this example

Step 4: Get all productions in GNF

Consider

$A_1 =\gt A_1A_2A_3$

$A1 =\gt aA_2A_2A_3 \ (as \ A_2 =\gtaA_2) \ \ is \ a \ GNF$

Consider

$A_1 =\gt A_2A_3$

$A1 =\gt a A_2A_3 \ (as \ A_2 =\gt aA_2) \ is \ a \ GNF$

Consider

$A_1 =\gt A_3A_3$

$A_1 =\gt bA_3A_3 \ (as A_3 =\gtbA_3) \ is \ a \ GNF$

Consider

$A_1 =\gt A_2A_2$

$A_1 =\gt aA_2A_2 \ (as \ A_2 =\gt aA_2) \ is \ a \ GNF$

Consider

$A_1 =\gt A_2$

$A_1 =\gtaA_2 \ (as \ A_2 =\gt aA_2) \ is \ a \ GNF$

Consider

$A_1 =\gt A_3$

$A_1 =\gt bA_3 \ (as \ A_3 =\gtbA_3) \ is \ a \ GNF$