The document Normal Forms for CFGs Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Theory of Computation.

All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

**Part III. Normal Forms for CFGs**

Standard form or normal forms have been developed for context free grammars. Any CFG can be converted to these forms.

The advantages of representing a CFG in this form are,

1. Complexity of the CFG will be less, and

2. It will be easier to implement the CFG.

Two commonly used normal forms for CFGs are,

1. Chomsky normal form (CNF), and

2. Greibach normal form (GNF).

4 Chomsky Normal Form (CNF)

A context free grammar, G is in Chomsky Normal Form, if every production is of the form,

A → a,

A → BC,

S → ε; for this production, S is the start symbol.

Thus the RHS of a production can be a single terminal, or two non-terminals. Also it can be ε, if LHS is the start symbol.

**Example 1:**

Following CFG is in Chomsky normal form (CNF):

S→ AB|b|ε,

A→ BC|a,

B→ b,

C→ c

where S is the start symbol.

**Example 2:**

Following CFG is not in Chomsky normal form (CNF):

S→ ASB|AB|b,

A→ BC|a,

A→ a,

B→ bb

where S is the start symbol.

The above is not in CNF because the productions,

S→ ASB,

B→ bb

do not satisfy the conditions of CNF.

**4.1 Conversion to CNF**

Every CFG can be reduced to CNF. Following examples show how this is done.

**Example 1:**

Consider the following CFG,

S→ bA|aB,

A→ bAA|aS|a,

B→ aBB|bS|b

where S is the start symbol.

Convert this CFG to CNF.

Consider the production,

S→ bA|aB

This is not in CNF. So replace ’b’ by non-terminal, P and ’a’ by non-terminal, Q. Thsi is by adding the productions,

P→ b, Q→ a.

,Then we get,

S→ P A|QB

P→ b

Q→ a

Now the CFG becomes,

S→ P A|QB

P→ b

Q→ a

A→ P AA|QS|a,

B→ QBB|P S|b

In the above the productions,

A→ P AA,

B→ QBB

are not in CNF. So replace AA by R and BB by T. this is done by adding the productions, R→ AA, T→ BB.

Then we get,

A→ P R,

B→ QT

R→ AA,

T→ BB

Now the CFG becomes,

S→ P A|QB

P→ b

Q→ a

A→ P R|QS|a,

B→ QT|P S|b

R→ AA,

T→ BB

where S is the start symbol.

Note that above CFG is in CNF.

**Example 2:**

Consider the following CFG,

S→ 1A|0B,

A→ 1AA|0S|0,

B→ 0BB|1

where S is the start symbol.

Convert this CFG to CNF.

Consider the production, S→ 1A|0B,

This is not in CNF. So replace 1 by P and 0 by Q, by adding the productions, P→ 1, Q→ 0,

we get,

S→ P A|QB

P→ 1

Q→ 0

Now the CFG is,

S→ P A|QB

P→ 1

Q→ 0

A→ P AA|QS|0,

B→ QBB|1

In the above CFG, the productions,

A→ P AA

B→ QBB

are not in CNF.

So replace AA by R and BB by T. Then we get,

A→ P R

B→ QT

R→ AA

T→ BB

Now the CFG is,

S→ P A|QB

P→ 1

Q→ 0

A→ P R|QS|0,

B→ QT|1

R→ AA

T→ BB

where S is the start symbol.

Above CFG is in CNF.

**Example 3:**

Consider the following CFG,

S→ a|b|CSS,

where S is the start symbol.

Convert this CFG to CNF.

In the above, the production, S→ CSS,

is not in CNF. So replace SS by P, we get,

S→ CP

P→ SS

Now the CFG becomes,

S→ a|b|CP

P→ SS

where S is the start symbol.

Above CFG is in CNF.

**Example 4:**

Consider the following CFG,

S→ abSb|a|aAb,

A→ bS|aAAb,

where S is the start symbol.

Convert this CFG to CNF.

Consider the production, S→ abSb|aAb is not in CNF.

So replace Ab by P , we get,

S→ abSb|aP

P→ Ab

Now the grammar becomes,

S→ abSb|a|aP

P→ Ab

A→ bS|aAP

Now replace Sb by R, we get,

S→ abR|a|aP

P→ Ab

A→ bS|aAP

R→ Sb

Now replace bR with T, we get

S→ aT|a|aP

P→ Ab

A→ bS|aAP

R→ Sb

T→ bR

Now replace aA with U, we get,

S→ aT|a|aP

P→ Ab

A→ bS|UP

R→ Sb

T→ bR

U→ aA

Now replace a with V and b with W, we get,

S→ V T|a|V P

P→ AW

A→ W S|UP

R→ SW

T→ W R

U→ V A

V→ a

W→ b

where S is the start symbol.

The above CFG is in CNF.

**Exercises:**

Convert the following CFGs to CNF.

1.

S→ bA|aB

A→ bAA|aS|a

B→ aBB|bS|b

where S is the start symbol.

2.

S→ aAD

A→ aB|bAB

B→ b

D→ d

where S is the start symbol.

3.

S→ aAbB

A→ aA|a

B→ bB|b

where S is the start symbol.

4.

S→ aAbB

A→ Ab|b

B→ Ba|a

where S is the start symbol.

5.

S→ aA|bB

A→ bAA|a

B→ BBa|b

where S is the start symbol.

5.

S→ abSb|ab

where S is the start symbol.

**5 Greibach Normal Form (GNF)**

A context free grammar, G is in Greibach nromal form, if every production is of the form,

A→ aX

S→ ε, for this production, S should be start symbol.

where a is a single terminal,

X is a set of 0 or more non-terminals.

Example 1:

The following CFG is in Greibach normal form (GNF):

S→ aAB|ε

A→ bC

B→ b

C→ c

where S is the start symbol.

Example 2:

The following CFG is not in Greibach normal form (GNF):

S→ aAB

A→ BbC

B→ b|ε

C→ c

where S is the start symbol.

The above is not in GNF becuause the productions, A→ BbC, B→ ε do not satisfy the conditions of GNF.

**5.1 Conversion to GNF**

Every CFG can be converted to Greibach normal form (GNF).

Following are the steps:

Step 1: Convert the given CFG to CNF.

Rename all non-terminals by A_{1}, A2, ......An, where A_{1} is the start symbol.

Step 2: Modify the grammar so that every production is of the form,

Ai→ aγ, or

Ai→ A_{j}γ, where j>i, and

γ is a set of 0 or more non-terminals.

This can be done by performing a number of substitutions.

Now if a production is of the form,

A→ Aγ, it is in left recursive form.

This left recursion can be eliminated by using a new variable, Z.

This is done as follows:

Let there be a production, A→ ADF|Aa|a|b|c

This can be written as,

A→ a|b|c|aZ|bZ|cZ

Z→ DF|a|DFZ|aZ

In a production leftmost symbol of RHS must be a terminal as,

A_{n}→ αγ,

otherwise if it is of the form,

A_{n}→ A_{m}γ

then replace Am on RHS of production of A_{m−1} by replacement rule.

Thus in short, to convert a grammar to GNF, first start with grammar in CNF and then apply substitution rule and

eliminate left recursion.

**Example 1:**

Consider the CFG,

S→ AB|BC

A→ aB|bA|a

B→ bB|cC|b

C→ c

Convert this grammar to Greibach normal form (GNF).

The production, S→ AB|BC is not in GNF.

On applying the substitution rule we get,

S→ aBB|bAB|aB|bBC|cCC|bC

Now the CFG becomes,

S→ aBB|bAB|aB|bBC|cCC|bC

A→ aB|bA|a

B→ bB|cC|b

C→ c

**Example 2:**

Consider the CFG,

S→ abaSa|aba

Convert this grammar to Greibach normal form (GNF).

Replace a by A using the production, A→ a,

Replace b by B using the production, B→ b,

we get,

S→ aBASA|aBA

A→ a

B→ b

Now the above CFG is in GNF.

**Example 3:**

Consider the CFG,

S→ AB

A→ aA|bB|b

B→ b

Convert this grammar to Greibach normal form (GNF).

In the above CFG, the production,

S→ AB

is not in GNF.

So replace this by,

S→ aAB|bBB|bB

Now the CFG becomes,

S→ aAB|bBB|bB

A→ aA|bB|b

B→ b

The above CFG is in Greibach normal form.

**Example 4:**

Consider the CFG,

S→ abSb|aa

Convert this grammar to Greibach normal form (GNF).

The above production is not in GNF.

So introduce two productions,

A→ a

B→ b

Now the CFG becomes,

S→ aBSB|aA

A→ a

B→ b

Above CFG is in GNF.

**Example 5:**

Consider the CFG,

S→ aSa|bSb|aa|bb

Convert this grammar to Greibach normal form (GNF).

Introduce two productions,

A→ a

B→ b

Then the grammar becomes,

S→ aSP|bSQ|aP|bQ

A→ a

B→ b

Above CFG is in GNF.

**Example 6:**

Consider the CFG,

S→ AA|a

A→ SS|b

Convert this grammar to Greibach normal form (GNF).

Step 1:

Above CFG is in CNF.

Rename the variables, that is,

Rename S, A by A_{1}, A_{2}.

Then the grammar becomes,

A_{1}→ A_{2}A_{2}|a

A_{2}→ A_{1}A_{1}|b

Step 2: In this, productions must be of the form that

the RHS of a production must start with a terminal followed by nonterminals, or

the RHS of a production starts with a higher numbered variable.

The productions,

A_{1}→ A_{2}A_{2}|a

A_{2}→ b

satisfy this criterion.

Consider the production,

A_{2}→ A_{1}A_{1}

Replace the first A1 on the RHS by its production.

Then,

A_{2}→ A_{2}A_{2}A_{1}|aA_{1}

Now the CFG is,

A_{1}→ A_{2}A_{2}|a

A_{2}→ b

A_{2}→ A_{2}A_{2}A_{1}|aA_{1}

That is,

A_{1}→A_{2}A_{2}|a

A_{2}→ A_{2}A_{2}A_{1}|aA_{1}|b

The production,A_{2}→ A_{2}A_{2}A_{1}|aA_{1}|b contains left recursion.

To eliminate left recursion, this is written as,

A_{2}→ aA_{1}|b|aA_{1}Z|bZ

Z→ A_{2}A_{1}|A_{2}A_{1}Z

Now the CFG is,

A_{1}→ A_{2}A_{2}|a

A_{2}→ aA_{1}|b|aA_{1}Z|bZ

Z→ A_{2}A_{1}|A_{2}A_{1}Z

Consider the production, A_{1}→A_{2}A_{2}

Replace first A_{2} on the RHS with its production, we get,

A_{1}→ aA_{1}A_{2}|bA_{2}|aA_{1}ZA2|bZA_{2}

Now the CFG is

A_{1}→ aA_{1}A_{2}|bA_{2}|aA_{1}ZA_{2}|bZA_{2}

A_{2}→ aA_{1}|b|aA_{1}Z|bZ

Z→ A_{2}A_{1}|A_{2}A_{1}Z

Consider the production, Z→ A_{2}A_{1}|A_{2}A_{1}Z

Replace first A2 on the RHS with its production,

Z→ aA_{1}A_{1}|aA_{1}A_{1}Z|bA_{1}|bA_{1}Z|aA_{1}ZA_{1}|aA_{1}ZA_{1}Z|bZA_{1}|bZA_{1}Z

Now the CFG is,

A_{1}→ aA_{1}A_{2}|bA_{2}|aA_{1}ZA_{2}|bZA_{2}

A_{2}→ aA_{1}|b|aA_{1}Z|bZ

Z→ aA_{1}A_{1}|aA_{1}A_{1}Z|bA_{1}|bA_{1}Z|aA_{1}ZA_{1}|a_{A1}ZA_{1}Z|bZA_{1}|bZA_{1}Z

Above CFG is in GNF.

**Example 8:**

Consider the CFG,

S→ AB

A→ BS|a

B→ SA|b

Convert this grammar to Greibach normal form (GNF).

Step 1: The given grammar is in Chomsky normal form.

Rename the variables, that is,

Rename S, A, B by A_{1}, A_{2}, A_{3}.

Then the grammar becomes,

A_{1}→ A_{2}A_{3}

A_{2}→ A_{3}A_{1}|a

A_{3}→ A_{1}A_{2}|b

Step 2: In this, productions must be of the form that

the RHS of a production must start with a terminal followed by nonterminals, or

the RHS of a production starts with a higher numbered variable.

The productions,

A_{1}→ A_{2}A_{3}

A_{2}→ A_{3}A_{1}|a

A_{3}→ b

satisfy this criterion.

But the production,

A_{3}→ A_{1}A_{2} does not satisfy this.

By applying substitution rule, substitute for A_{1} as

A_{3}→ A_{2}A_{3}A_{2}

substitute for A_{2} as

A_{3}→ A_{3}A_{1}A3A_{2}|aA_{3}A_{2}

Now the CFG is,

A_{1}→ A_{2,}A_{3}

A_{2}→ A_{3}A_{1}|a

A_{3}→ A_{3}A_{1}A_{3}A_{2}|aA_{3}A_{2}|b

Consider the production,

A_{3}→ A_{3}A_{1}A_{3}A_{2}|aA_{3}A_{2}|b

Eliminating left recursion from the above production, we get,

A_{3}→ aA_{3}A_{2}B_{3}|bB_{3}|aA_{3}A_{2}|b

B_{3}→ A_{1}A_{3}A_{2}B_{3}|A_{1}A_{3}A_{2}

Now we have the productions,

A_{1}→ A_{2}A_{3}

A_{2}→ A_{3}A_{1}|a

A_{3}→ aA_{3}A_{2}B_{3}|bB_{3}|aA_{3}A_{2}|b

B_{3}→ A_{1}A_{3}A_{2}B_{3}|A_{1}A_{3}A_{2}

Now all the A3 productions start with terminals.

Using substitution rule, replace A_{3} in the RHS of the production for A_{2}.

A_{2}→ A_{3}A_{1}|a becomes,

A_{2}→ aA_{3}A_{2}B_{3}A_{1}|bB_{3}A_{1}|aA_{3}A_{2}A_{1}|bA_{1}|a

Now the CFG is,

A_{1}→ A2A_{3}

A_{2}→ aA_{3}A_{2}B_{3}A_{1}|bB_{3}A_{1}|aA_{3}A_{2}A_{1}|bA_{1}|a

A_{3}→ aA_{3}A_{2}B_{3}|bB_{3}|aA_{3}A_{2}|b

B_{3}→ A_{1}A_{3}A_{2}B_{3}|A_{1}A_{3}A_{2}

Using substitution rule, replace A_{2} in the RHS of the production for A_{1}.

A_{1}→ aA_{3}A_{2}B_{3}A_{1}A_{3}|bB_{3}A_{1}A_{3}|aA_{3}A_{2}A_{1}A_{3}|bA_{1}A_{3}|aA_{3}

Now the CFG is,

A_{1}→ aA_{3}A_{2}B_{3}A_{1}A_{3}|bB_{3}A_{1}A_{3}|aA_{3}A_{2}A_{1}A_{3}|bA_{1}A_{3}|aA_{3}

A_{2}→ aA_{3}A_{2}B_{3}A_{1}|bB_{3}A_{1}|aA_{3}A_{2}A_{1}|bA_{1}|a

A_{3}→ aA_{3}A_{2}B_{3}|bB_{3}|aA_{3}A_{2}|b

B_{3}→ A_{1}A_{3}A_{2}B_{3}|A_{1}A_{3}A_{2}

Using substitution rule, replace A_{1} in the RHS of the production for B_{3}.

B_{3}→aA_{3}A_{2}B_{3}A_{1}A_{3}A_{3}A_{2}B_{3}|aA_{3}A_{2}B_{3}A_{1}A_{3}A_{3}A_{2}|bB_{3}A_{1}A_{3}A_{3}A_{2}B_{3}|bB_{3}A_{1}A_{3}A_{3}A_{2}|aA_{3}A_{2}A_{1}A_{3}A_{3}A_{2}B_{3}|aA_{3}A_{2}A_{1}A_{3}A_{3}A_{2}|bA_{1}A_{3}A_{3}A_{2}B_{3}|bA_{1}A_{3}A_{3}A_{2}|aA_{3}A_{3}A_{2}B_{3}|aA_{3}A_{3}A_{2}

Now the CFG is,

A_{1}→ aA_{3}A_{2}B_{3}A_{1}A_{3}|bB_{3}A_{1}A_{3}|aA_{3}A_{2}A_{1}A_{3}|bA_{1}A_{3}|aA_{3}

A_{2}→ aA_{3}A_{2}B_{3}A_{1}|bB_{3}A_{1}|aA_{3}A_{2}A_{1}|bA_{1}|a

A_{3}→ aA_{3}A_{2}B_{3}|bB_{3}|aA_{3}A_{2}|b

B_{3 }→aA_{3}A_{2}B_{3}A_{1}A_{3}A_{3}A_{2}B_{3}|aA_{3}A_{2}B_{3}A_{1}A_{3}A_{3}A_{2}|bB_{3}A_{1}A_{3}A_{3}A_{2}B_{3}|bB_{3}A_{1}A_{3}A_{3}A_{2}|aA_{3}A_{2}A_{1}A_{3}A_{3}A_{2}B_{3}|aA_{3}A_{2}A_{1}A_{3}A_{2}A_{1}A_{3}A_{3}A_{2}|bA_{1}A_{3}A_{3}A_{2}B_{3}|bA_{1}A_{3}A_{3}A_{2}|aA_{3}A_{3}A_{2}B_{3}|aA_{3}A_{3}A_{2}

Above CFG is in Greibach normal form.

**Exercises:**

1.

Consider the CFG,

A→ aBD|bDB|c|AB|AD

Convert this grammar to Greibach normal form (GNF).

2.

Consider the CFG,

S→ AB

A→ BS|b

B→ SA|a

Convert this grammar to Greibach normal form (GNF).

3.

Consider the CFG,

E→ E + T|T

T→ T ∗ F|F

F→ (E)|a

Convert this grammar to Greibach normal form (GNF).

4.

Consider the CFG,

S→ Y Y |0

Y→ SS|1

Convert this grammar to Greibach normal form (GNF).

5.

Consider the CFG,

S→ XY

X→ Y S|1

Y→ SX|0

Convert this grammar to Greibach normal form (GNF).

6.

Consider the CFG,

S→ XY

X→ 0X|1Y |1

Y→ 1

Convert this grammar to Greibach normal form (GNF).

7.

Consider the CFG,

S→ 01S1|11

Convert this grammar to Greibach normal form (GNF).

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

18 videos|43 docs|39 tests