The document Simplification of Context Free Grammars 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 II. Simplification of Context Free Grammars****3 Simplification of CFGs**

We can simplify a CFG and produce an equivalent reduced CFG. This is done by,

a. Eliminating useless symbols,

b. Eliminating ε productions,

c. Eliminating unit productions.

**3.1 Eliminating Useless Symbols**

Useless symbols are those non-terminals or terminals that do not appear in any derivation of a string.

A symbol, Y is said to be useful if:

that is Y should lead to a set of terminals. Here Y is said to be ’generating’.

b. If there is a derivation,

then Y is said to be ’reachable’.

Thus a symbol is useful, if it is ’generating’ and ’useful’.

Thus a symbol is useless, if it is not ’generating’ and not ’reachable’.

**Example 1:**

Consider the CFG,

S → AB|a

A → b

where S is the start symbol.

Eliminate uselss symbols from this grammar.

By observing the above CFG, it is clear that B is a non generating symbol. Since A derives ’b’, S derives ’a’ but B does not derive any string ’w’.

So we can eliminate S → AB from the CFG.

Now CFG becomes,

S → a

A → b

Here A is a non reachable symbol, since it cannot be reached from the start symbol S.

So we can eliminate the production, A → b from the CFG.

Now the reduced grammar is,

S → a

This grammar does not contain any useless symbols.

**Example 2:**

Consider the CFG,

S → aB|bX

A → BAd|bSX|a

B → aSB|bBX

X → SBD|aBx|ad

where S is the start symbol.

Eliminate uselss symbols from this grammar.

First we choose those non terminals which derive to the strings of terminals.

The non terminals,

A derives to the terminal ’a’;

X derives to the terminals ’ad’.

So A and X are useful symbols.

Since,

S → bX, and X is a useful symbol, S is also a useful symbol.

From the production, B → aSB|bBX,

B does not derive any terminal string, B is a non-generating symbol. So eliminate those productions containing B.

Grammar becomes,

S → bX

A → bSX|a

X → ad

From the above CFG, A is a non- reachable symbol, since A cannot be reached from the start symbol, S.

So eliminate the production, A → bSX|a.

Now the CFG is,

S → bX

X → ad

This grammar does not contain any useless symbols.

**Example 3:**

Consider the CFG,

A → xyz|Xyzz

X → Xz|xY z

Y → yY y|Xz

Z → Zy|z

where A is the start symbol.

Eliminate uselss symbols from this grammar.

From the productions,

A → xyz, Z → z,

A and Z derive to the strings of terminals. So A and Z are useful symbols.

X and Y do not lead to a string of terminals; that means X and Y are useless symbols.

Eliminating the productions of X and Y, we get,

A → xyz

Z → Zy|z

From the above, Z is not reachable, since it cannot be reached from the start symbol, A. So eliminate the production

corresponding to Z.

The CFG is,

A → xyz.

This grammar does not contain any useless symbols.

**Example 4:**

Consider the CFG,

S → aC|SB

A → bSCa

B → aSB|bBC

C → aBC|ad

where S is the start symbol.

Eliminate uselss symbols from this grammar.

Since, C → ad,

C is a generating symbol.

Since, S → aC,

S is also a useful symbol.

Since, A → bSCa,

A is also a useful symbol.

The RHS of B → aSB|bBC contains B. B is not terminating. B is not generating.

So B is a useless symbol. Eliminate those productions containing B.

We get,

S → aC

A → bSCa

C → ad

From the above, A is not reachable, since it cannot be reached from the start symbol, S.

So eliminate the production corresponding to A.

We get the CFG as,

S → aC

C → ad

where S is the start symbol.

This grammar does not contain any useless symbols.

**3.2 Removal of Unit Productions**

A unit production is defined as,

A → B

where A is a non-terminal, and

B is a non-terminal.

Thus both LHS and RHS contain single non-terminals.

Following examples show how unit productions are removed from a CFG.

**Example 1:**

Consider the CFG,

S → AB

3 Simplification of CFGs 20

A → a

B → C|b

C → D

D → E

E → a

where S is the start symbol.

Eliminate unit productions from this grammar.

From the above CFG, it is seen that,

B → C

C → D

D → E

are unit productions.

To remove the production, B → C, check whether there exists a production whose LHS is C and RHS is a terminal.

No such production exists.

To remove the production, C → D, check whether there exists a production whose LHS is D and RHS is a terminal.

No such production exists.

To remove the production, D → E, check whether there exists a production whose LHS is E and RHS is a terminal.

There is a production, E → a. So remove, D → E, and add the production, D → a, CFG becomes,

S → AB

A → a

B → C|b

C → D

D → a

E → a

Now remove the production, C → D, and add the production, C → a, we get,

S → AB

A → a

B → C|b

C → a

D → a

E → a

Now remove the production, B → C, and add the production, B → a, we get,

S → AB

A → a

B → a|b

C → a

D → a

E → a

where S is the start symbol.

Now the grammar contains no unit productions.

From the above CFG, it is seen that the productions, C → a, D → a, E → a are useless becuse the symbols C, D and E cannot be reached from the start symbol, S.

By eliminating these productions, we get the CFG as,

S → AB

A → a

B → a|b

Above is a completely reduced grammar.

**Example 2:**

Consider the CFG,

S → a|b|Sa|Sb|S0|S1

F → S|(E)

T → F|T ∗ F

E → T|E + T

where E is the start symbol.

Eliminate unit productions from this grammar.

From the above CFG,

F → S

T → F

E → T

are unit productions.

The unit production F → S can be removed by rewriting it as, F → a|b|Sa|Sb|S0|S1

Now the CFG is,

S → a|b|Sa|Sb|S0|S1

F → a|b|Sa|Sb|S0|S1|(E)

T → F|T ∗ F

E → T|E + T

The unit production T → F can be removed by rewriting it as, T → a|b|Sa|Sb|S0|S1|(E)

Now the CFG is,

S → a|b|Sa|Sb|S0|S1

F → a|b|Sa|Sb|S0|S1|(E)

T → a|b|Sa|Sb|S0|S1|(E)|T ∗ F

E → T|E + T

The unit production E → T can be removed by rewriting it as, E → a|b|Sa|Sb|S0|S1|(E)|T ∗ F

Now the CFG is,

S → a|b|Sa|Sb|S0|S1

F → a|b|Sa|Sb|S0|S1|(E)

T → a|b|Sa|Sb|S0|S1|(E)|T ∗ F

E → a|b|Sa|Sb|S0|S1|(E)|T ∗ F|E + T

This is the CFG that does not contain any unit productions.

**Example 1:**

Consider the CFG,

S → A|bb

A → B|b

B → S|a

where S is the start symbol.

Eliminate unit productions from this grammar.

Here unit productions are,

S → A

A → B

B → S

Here,

S → A generates S → b

S → A → B generates S → a

A → B generates A → a

A → B → S generates A → bb

B → S generates B → bb

B → S → A generates B → b

The new CFG is,

S → b|a|bb

A → a|bb|b

B → bb|b|a

which contains no unit productions.

**3.3 Removal of ε- Productions**

Productions of the form, A → ε are called ε -productions.

We can eliminate ε -productions from a grammar in the following way:

If A → ε is a production to be eliminated, then we look for all productions, whose RHS contains A, and replace every

occurrence of A in each of these productions to obtain non ε -productions. The resultant non ε -productions are added to

the grammar.

**Example 1:**

Consider the CFG,

S → aA

A → b|ε

where S is the start symbol.

Eliminate epsilon productions from this grammar.

Here, A → ε is an epsilon production.

By following the above procedure, put ε in place of A, at the RHS of productions, we get,

The production, S → aA becomes, S → a.

Then the CFG is,

S → aA

S → a

A → b

OR

S → aA|a

A → b

Thus this CFG does not contain any epsilon productions.

**Example 2:**

Consider the CFG,

S → ABAC

A → aA|ε

B → bB|ε

C → c

where S is the start symbol.

Eliminate epsilon productions from this grammar.

This CFG contains the epsilon productions, A → ε, B → ε.

To eliminate A → ε, replace A with epsion in the RHS of the productions, S → ABAC, A → aA,

For the production, S → ABAC, replace A with epsilon one by one as,

we get,

S → BAC

S → ABC

S → BC

For the production, A → aA, we get,

A → a,

Now the grammar becomes,

S → ABAC|ABC|BAC|BC

A → aA|a

B → bB|ε

C → c

To eliminate B → ε, replace A with epsion in the RHS of the productions, S → ABAC, B → bB,

For the production, S → ABAC|ABC|BAC|BC , replace B with epsilon as,

we get,

S → AAC|AC|C

For the production, B → bB, we get,

B → b,

Now the grammar becomes,

S → ABAC|ABC|BAC|BC|AAC|AC|C

A → aA|a

B → bB|b

C → c

which does not contain any epsilon production.

**Example 3:**

Consider the CFG,

S → aSa

3 Simplification of CFGs 25

S → bSb|ε

where S is the start symbol.

Eliminate epsilon productions from this grammar.

Here, S → ε is an epsilon production. Replace the occurrence of S by epsilon, we get,

S → aa,

S → bb

Now the CFG becomes,

S → aSa|bSb|aa|bb

This does not contain epsilon productions.

**Example 4:**

Consider the CFG,

S → a|Xb|aY a

X → Y |ε

Y → b|X

where S is the start symbol.

Eliminate epsilon productions from this grammar.

Here, X → ε is an epsilon production. Replace the occurrence of X by epsilon, we get,

S → a|b

X → Y

Y → ε

Now the grammar becomes,

S → a|Xb|aY a|a|b

X → Y

Y → b|X|ε

In the above CFG, Y → ε is an epsilon production. Replace the ocurrence of Y by epsilon, we get,

S → aa

X → ε

Now the grammar becomes,

S → a|Xb|aY a|a|b|aa

X → Y

Y → b|X

This grammar does not contain epsilon productions.

Exercises:

Simplify the following context free grammars:

1.

S → AB

A → a

B → b

B → C

E → c|ε

where S is the start symbol.

2.

S → aAa

A → Sb|bCC|DaA

C → abb|DD

E → aC

D → aDA

where S is the start symbol.

3.

S → bS|bA|ε

A → ε

where S is the start symbol.

4.

S → bS|AB

A → ε

B → ε

D → a

where S is the start symbol.

5.

S → A

A → B

B → C

C → a

where S is the start symbol.

3 Simplification of CFGs 27

6.

S → AB

A → a

B → C|b

C → D

D → E

E → a

where S is the start symbol.

7.

S → ABCD

A → a

B → C|b

C → D

D → c

where S is the start symbol.

8.

S → aS|AC|AB

A → ε

C → ε

B → bB|bb

D → c

where S is the start symbol.

9.

S → ABC|A0A

A → 0A|B0C|000|B

B → 1B1|0|D

C → CA|AC

D → ε

where S is the start symbol.

10.

S → AAA|B

A → 0A|B

B → ε

where S is the start symbol.

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

18 videos|43 docs|39 tests