Greibach Normal Form

In Greibach Normal Form, there is restriction on the position, in which, terminals and variables can appear on right-hand side of production rules. In Greibach Normal Form, every production must start with a single terminal followed by any number of variables.

A Context Free Grammar (CFG) is in Greibach Normal Form, if the production rules are in the following form

In this where A, B1………Bn are any number of non-terminals, and a is a terminal used in Greibach Normal Form.

Example of Greibach Normal Form:

In this, A, B,C are non-terminals and a,b is a terminal

Steps to convert Context Free Grammar to Greibach Normal Form (GNF)

  • Check, if the given Context Free Grammar has any Unit productions or Null productions, and remove those Unit productions or Null productions.
  • Check whether the given Context Free Grammar is already in Chomsky Normal Form, and convert into Chomsky Normal Form, if it is not.
  • In this step, we have all the productions in the form some Ai where Ai is in ascending order of i.
  • In this step, we modify all the productions of the form Ai -> Aj X, then i < j and it should never be i >= j.
  • In this step, we remove all left Recursion in production rules.

Example:

Convert the following Context Free Grammar to Greibach Normal Form (GNF)

S -> CA

S -> BB

B -> b

B -> SB

A -> a

Solution:

Step 1:

In above given production rules there are no unit production and null production so, no need to perform the step1.

Step 2:

In step 2, the given grammar is already in Chomsky Normal form, so we can skip this step.

Step 3:

In this step we have all the productions in the form some Ai where Ai is in ascending order of i.

Replace S variable with A1

Replace C variable with A2

Replace A variable with A3

Replace B variable with A4

After replacing the symbol using Ai where i is 1 to 4 we get the new production rules as:

A1 -> A2A3 | A4A4

A4 -> b | A1A4

A2 -> b

A3 -> a

Step 4:

In this step, we modify all the productions of the form Ai -> Aj X, then i < j, and should never be i >= j.

where Ai  = A1 (L.H.S) and Aj = A2 (R.H.S)

For 1st production:

 A1 -> A2A3 | A4A4

1 < 2 i.e. ( i < j)

1 < 4 i.e. ( i < j) it follows the step 4

For 2nd production:

A4 -> b | A1A4

As we know, if non-terminal symbol directly gives the terminal symbol, then it is already in Greibach Normal Form (GNF)

Now second part i.e. A1A4

4 > 1 i.e. ( i > j)

A4 -> b | A1A4

A4 -> b | A2A3 A4 |A4 A4 A4        [Replace     A4 A4       with A1] 

Now, see whether they follow the rule or not.

I = 4 , j = 2

i > j [Not follow]

A4 -> b | A2A3 A4 |A4A4A4       

A4 -> b | A2A3 A4 |A4A4A4        [again A2 create problem]

A4 -> b | bA3 A4 |A4A4A4       [bA3 A4 this part in GNF]

Now check the third half i.e. A4A4A4      

In this part we get i = j (i.e. 4 = 4)     

 A4 -> b | bA3 A4 |A4A4A4 [first A4 is left recursive]

According to the rule of GNF, if non-terminal symbol is followed by terminal symbol and further that terminal is followed by any other non-terminal symbol, then it is in GNF.

Step 5:

In this step we remove a left Recursion. Introduce a new variable to remove the left recursion.

A4 -> b | bA3 A4 |A4A4A4     

[This is a problem here, we don’t have variable or terminal symbol]

Introduce the new variable = Z, to remove the left recursion.

A4 -> b | bA3 A4 |A4A4A4      

Z -> A4A4Z | A4A4       

A4 -> b | bA3 A4 |bZ| bA3 A4 Z

Now, the new grammar is:

A1 -> A2A3 | A4A4

A4 -> b | bA3 A4 | bZ | bA3A4Z

Z -> A4A4 | A4A4Z

A2 -> b

A3 -> a

In A1 -> A2A3

In GNF, we don’t allow to have a variable in the beginning, so, we remove A2 variable with b terminal in the beginning.

In this way, we successfully have completed our conversion and the grammar we have is successfully converted into Greibach Normal Form.

Pin It on Pinterest

Share This