Courses

# Normal Forms for CFGs Computer Science Engineering (CSE) Notes | EduRev

## Computer Science Engineering (CSE) : Normal Forms for CFGs Computer Science Engineering (CSE) Notes | EduRev

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.
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 A1, A2, ......An, where A1 is the start symbol.

Step 2: Modify the grammar so that every production is of the form,
Ai→ aγ, or
Ai→ Ajγ, 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,
An→ αγ,
otherwise if it is of the form,
An→ Amγ
then replace Am on RHS of production of Am−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 A1, A2.
Then the grammar becomes,
A1→ A2A2|a
A2→ A1A1|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,
A1→ A2A2|a
A2→ b
satisfy this criterion.
Consider the production,
A2→ A1A1
Replace the first A1 on the RHS by its production.
Then,
A2→ A2A2A1|aA1
Now the CFG is,
A1→ A2A2|a
A2→ b
A2→ A2A2A1|aA1
That is,

A1→A2A2|a
A2→ A2A2A1|aA1|b
The production,A2→ A2A2A1|aA1|b contains left recursion.
To eliminate left recursion, this is written as,
A2→ aA1|b|aA1Z|bZ
Z→ A2A1|A2A1Z
Now the CFG is,
A1→ A2A2|a
A2→ aA1|b|aA1Z|bZ
Z→ A2A1|A2A1Z
Consider the production, A1→A2A2
Replace first A2 on the RHS with its production, we get,
A1→ aA1A2|bA2|aA1ZA2|bZA2
Now the CFG is
A1→ aA1A2|bA2|aA1ZA2|bZA2
A2→ aA1|b|aA1Z|bZ
Z→ A2A1|A2A1Z

Consider the production, Z→ A2A1|A2A1Z
Replace first A2 on the RHS with its production,
Z→ aA1A1|aA1A1Z|bA1|bA1Z|aA1ZA1|aA1ZA1Z|bZA1|bZA1Z
Now the CFG is,

A1→ aA1A2|bA2|aA1ZA2|bZA2
A2→ aA1|b|aA1Z|bZ
Z→ aA1A1|aA1A1Z|bA1|bA1Z|aA1ZA1|aA1ZA1Z|bZA1|bZA1Z

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 A1, A2, A3.
Then the grammar becomes,
A1→ A2A3
A2→ A3A1|a
A3→ A1A2|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,
A1→ A2A3
A2→ A3A1|a
A3→ b
satisfy this criterion.
But the production,
A3→ A1A2 does not satisfy this.
By applying substitution rule, substitute for A1 as
A3→ A2A3A2

substitute for A2 as

A3→ A3A1A3A2|aA3A2
Now the CFG is,
A1→ A2,A3
A2→ A3A1|a
A3→ A3A1A3A2|aA3A2|b
Consider the production,
A3→ A3A1A3A2|aA3A2|b
Eliminating left recursion from the above production, we get,
A3→ aA3A2B3|bB3|aA3A2|b
B3→ A1A3A2B3|A1A3A2
Now we have the productions,
A1→ A2A3
A2→ A3A1|a
A3→ aA3A2B3|bB3|aA3A2|b
B3→ A1A3A2B3|A1A3A2
Using substitution rule, replace A3 in the RHS of the production for A2.
A2→ A3A1|a becomes,
A2→ aA3A2B3A1|bB3A1|aA3A2A1|bA1|a

Now the CFG is,
A1→ A2A3
A2→ aA3A2B3A1|bB3A1|aA3A2A1|bA1|a
A3→ aA3A2B3|bB3|aA3A2|b
B3→ A1A3A2B3|A1A3A2
Using substitution rule, replace A2 in the RHS of the production for A1.
A1→ aA3A2B3A1A3|bB3A1A3|aA3A2A1A3|bA1A3|aA3
Now the CFG is,
A1→ aA3A2B3A1A3|bB3A1A3|aA3A2A1A3|bA1A3|aA3
A2→ aA3A2B3A1|bB3A1|aA3A2A1|bA1|a
A3→ aA3A2B3|bB3|aA3A2|b
B3→ A1A3A2B3|A1A3A2
Using substitution rule, replace A1 in the RHS of the production for B3.
B3→aA3A2B3A1A3A3A2B3|aA3A2B3A1A3A3A2|bB3A1A3A3A2B3|bB3A1A3A3A2|aA3A2A1A3A3A2B3|aA3A2A1A3A3A2|bA1A3A3A2B3|bA1A3A3A2|aA3A3A2B3|aA3A3A2

Now the CFG is,
A1→ aA3A2B3A1A3|bB3A1A3|aA3A2A1A3|bA1A3|aA3
A2→ aA3A2B3A1|bB3A1|aA3A2A1|bA1|a
A3→ aA3A2B3|bB3|aA3A2|b

B→aA3A2B3A1A3A3A2B3|aA3A2B3A1A3A3A2|bB3A1A3A3A2B3|bB3A1A3A3A2|aA3A2A1A3A3A2B3|aA3A2A1A3A2A1A3A3A2|bA1A3A3A2B3|bA1A3A3A2|aA3A3A2B3|aA3A3A2
Above CFG is in Greibach normal form.

Exercises:
1.
Consider the CFG,
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!

## Theory of Computation

18 videos|43 docs|39 tests

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;