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
1
2
3
4
|
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:
1
2
3
4
|
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 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.
1
2
3
4
5
6
7
|
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.