Automata Greibach Normal Form

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

A -> a
A -> aB1, B2………Bn

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:

A -> bBC
B -> a

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 A_i where A_i 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 A_i where A_i 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 A_i 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.

A4 -> bA3 |bA4 | bA3 A4A4 | bZA4 | bA3 A4Z
 A4 -> b|bA3A4 |bZ | bA3 A4Z
 Z -> bA4|bA3A4A4 |bZA4 | bA3 A4ZA4 | bA4Z | bA3A4A4Z | bZA4Z | bA3A4ZA4Z
 A2 -> b //Already in GNF
 A3 -> a //Already in GNF 

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