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 byZ → α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$