Greibach Normal Form (GNF)

In this class, We discuss Greibach Normal Form (GNF).

For Complete YouTube Video: Click Here

The reader should have prior knowledge of Chomsky’s normal form. Click Here.

Greibach Normal Form: A given CFG is greibach normal form. if the productions are of the form

A – aα where α may be any number of non-terminals.

A – a where a is any terminal symbol

To convert the CFG into GNF, we follow the steps.

Using GNF, we can make the decision easily. because the first symbol is a terminal.

Example:

S – AB

A – BS | b

B – SA | a

First: convert CFG to CNF.

The CFG is in CNF., so there is no need for the first step in our example.

Second Step:

Give non-terminals a separate naming.

S is assigned A1

A is assigned A2

B is assigned A3

Substitute the naming in the CFG.

A1 – A2A3

A2 – A3A1 | b

A3 – A1A2 | a

Check productions of the form Ai – Aj where i <= j

The production A3 – A1A2 | a is not in the given form.

In the production A3 – A1A2 | a i = 3, and j = 1. where i > j.

Using substitution, we need to bring the production to satisfy the condition i <= j..

Substitute A1 in the production A3.

A3 – A2A3A2 | a

we substitute the production A2 in the production A3.

A3 – A3A1A3A2 | a | bA3A2

The above production is in left recursion.

Third Step:

Eliminate Left recursion.

Here α is A1A3A2, and β is a | bA3A2

The below grammar shows CFG after eliminating left recursion.

A3 – aZ3 | bA3A2Z3

Z3 – A1A3A2Z3 | ε

Now the production A3 is in GNF.

Using substitution brings back all the productions to GNF.

Substitute A3 to the production A2.

A2 – b | aZ3A1 | bA3A2Z3A1 | aA1 | bA3A2A1

Now, we substitute A2 to the production A1. The production A2 is in GNF.

A1 – bA3 | aZ3A1A3 | bA3A2Z3A1A3 | aA1A3 | bA3A2A1A3

Now we can substitute A1 in production Z3. the production A1 is in GNF.

The reader can continue substituting A1 in Z3.

Finally, We got all the productions in GNF.