# 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**.