S => ABA | AB | BA | AA | A | B

A => aA | b

B => bB | b

SOLUTION:

• 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

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

o 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 A1A1, A be A2A2, B be A3A3

The grammar now becomes

A1=>A1A2A3 | A2A3 | A3A3 | A2A2 | A2 | A3A1=>A1A2A3 | A2A3 | A3A3 | A2A2 | A2 | A3

A2=>aA2 | aA2=>aA2 | a

A3=>bA3 | bA3=>bA3 | b

Step 2: For each Ai=>AjAi=>Aj, 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

A1=>A1A2A3A1=>A1A2A3

A1=>aA2A2A3 (as A2=\gtaA2) is a GNFA1=>aA2A2A3 (as A2=\gtaA2) is a GNF

Consider

A1=>A2A3A1=>A2A3

A1=>aA2A3 (as A2=>aA2) is a GNFA1=>aA2A3 (as A2=>aA2) is a GNF

Consider

A1=>A3A3A1=>A3A3

A1=>bA3A3 (asA3=\gtbA3) is a GNFA1=>bA3A3 (asA3=\gtbA3) is a GNF

Consider

A1=>A2A2A1=>A2A2

A1=>aA2A2 (as A2=>aA2) is a GNFA1=>aA2A2 (as A2=>aA2) is a GNF

Consider

A1=>A2A1=>A2

A1=\gtaA2 (as A2=>aA2) is a GNFA1=\gtaA2 (as A2=>aA2) is a GNF

Consider

A1=>A3A1=>A3

A1=>bA3 (as A3=\gtbA3) is a GNF