V semester

Course Name: Theory of Computations

Course Code: BCS503
Credits: 4
Scheme:2022

MODULE-4

Course Instructor: Mrs. Divya U H

Assistant Professor
Department of CSE, EPCET
[email protected] (9481975333)
TOC(BCS503) Module 4 Notes

NORMAL FORMS FOR CONTEXT-FREE GRAMMARS

The goal of this section is to show that every CFL, without ϵ is generated by a
CFG in which all productions are of the form A→BC or A→a, where A, B, and
C are variables, and a is a terminal. This form is called Chomsky Normal Form.
To get there, we need to make a number of preliminary simplifications, which are
themselves useful in various ways.

1. We must eliminate ϵ-productions, those of the form A→ ϵ for some variable

A.
2. We must eliminate unit productions, those of the form A→B for variables
A and B.
3. We must eliminate useless symbols, those variables or terminals that do not
appear in any derivation of a terminal string from the start symbol.

1. Eliminating Useless Symbols:

Department of CSE, EPCET 2025-26 2

TOC(BCS503) Module 4 Notes

are reachable.

2. Eliminating ϵ-Productions:

Nullable Variable: A variable A is nullable if , A=>ϵ

Department of CSE, EPCET 2025-26 3

TOC(BCS503) Module 4 Notes

Eliminating Unit Productions:

Define Unit Production:

“A unit production is a production of the form A → B, where both A and B are variables.

Department of CSE, EPCET 2025-26 4

TOC(BCS503) Module 4 Notes

However, unit productions can complicate certain proofs and they also introduce
extra steps into derivations that technically need not be there.

Ex : A→B

B-> a | ab

Can be rewritten as, A→a | ab, by eliminating the unit production A→B.

Consider the context free grammar given below and remove unit production
for the same.

S->0A|1B|C

A->0S|00

B->1|A

C->01

Step 1:

S->C is unit production but while removing S->C we have to consider what C
gives so we can add a rule to S.

S->0A|1B|01

Step 2:

B->A is also unit production

B->1|0S|00

Finally, we can write CFG without unit production as follows −

S->0A|1B|01

A->0S|00

B->1|0S|00

Department of CSE, EPCET 2025-26 5

TOC(BCS503) Module 4 Notes

C->01

Therefore, the simplification involves following steps in the same order as

mentioned below:

1. Eliminate ϵ-productions
2. Eliminate unit productions
3. Eliminate useless symbols

Chomsky Normal Form (CNF):

Definition of CNF: Every nonempty CFL without ϵ has a grammar G in which all
productions are in one of the two simple forms, either:

1. A→BC, where A, B, and C, are each variable, or

2. A →a, where A is a variable and a is a terminal.

Also, G has no useless symbols. Such a grammar is said to be in Chomsky

Normal Form or CNF.

Steps to convert given CFG to CFN:

1. Eliminate ϵ-productions
2. Eliminate unit productions
3. Eliminate useless symbols
4. Put the resulting grammar to CNF
• Arrange all the bodies of length 2 or more consist only variables.
• Break bodies of length 3 or more into a cascade of productions, each
with a body consisting of two variables.

Example :

Convert the following grammar to CNF.

Department of CSE, EPCET 2025-26 6

TOC(BCS503) Module 4 Notes

S→ABa

A→aab

B→Ac

Ans:

Step 1: Eliminate ϵ-productions:

Given grammar doesn’t have any ϵ-productions.

Step 2: Eliminate unit productions

Given grammar doesn’t have any unit productions.

Step 3: Eliminate useless symbols

Given grammar doesn’t have any useless symbols.

Step 4: Convert to CNF

S→ABTa S→AD1
D1→BTa
A→TaTaTb A→Ta D2
D2→TaTb
B→ATc B→ATc
Ta→a Ta→a
Tb→b Tb→b
Tc→c Tc→c

Therefore, final grammar in CNF is G’=(V’, T’, S, P’)

Where V’={S, A, B}

T’={a, b}

S is the start symbol

P’={ S→AD1
D1→BTa

Department of CSE, EPCET 2025-26 7

TOC(BCS503) Module 4 Notes

A→Ta D2
D2→TaTb
B→ATc
Ta→a
Tb→b
Tc→c }

(Note: For More problems refer classwork)

The Pumping Lemma for Context-Free Languages:

The Size of Parse Trees:

Greibach Normal Forms(GNF):

A CFG G=(V, T, P, S) is said to be in Greibach Normal Form if all its productions

are of the form,

A→aα

where A is a variable, symbol ‘a’ is a terminal and α ϵ V*.

For example: Productions, A→d, S→aABCD are in GNF.

Department of CSE, EPCET 2025-26 8

TOC(BCS503) Module 4 Notes

1. Consider the following Grammar G. Convert it into GNF.

S → AA | BC (1)
A → a|BA (2)
B→a (3)
C→c (4)
Here Productions, A → a
B→a
C → c are already in GNF.
Lets consider, A→BA and replace B by (3),
A→aA | a (5)
Now consider, S → AA | BC and replace 1st A by new productions (5) and
B by (3),
S→aAA | aA | aC

Therefore Productions in GNF are,

S→aAA | aA | aC
A→aA | a
B→a
C→c

Statement of the Pumping Lemma for CFL:

Department of CSE, EPCET 2025-26 9

TOC(BCS503) Module 4 Notes

Proof:

Department of CSE, EPCET 2025-26 10

TOC(BCS503) Module 4 Notes

Department of CSE, EPCET 2025-26 11

TOC(BCS503) Module 4 Notes

Application of Pumping Lemma

The pumping lemma for CFL’s is used to prove that certain languages are not
context free languages.

The general strategy used to prove that a given language is not context free is as
follows:

1. Assume that the language L is infinite and is context free.

2. Select the string say z and break it into sub strings u,v,w,x and y such that
z=uvwxy where,
|vwx|≤ & vx≠ϵ
3. Find any i such that uvi wxi y ∉ L. According to pumping lemma,

Department of CSE, EPCET 2025-26 12

TOC(BCS503) Module 4 Notes

uvi wxi y ϵ L. So the result is a contradiction to the assumption that the

language is context-free. Thus, we can prove that the given language L is
not contest-free.

Example:
Show that L={ anbncn :n>=1} is not context free.
Ans:
Let L is context free. Let z= anbncn ϵ L
Since |z|=3n>=n, we can split z into uvwxy such that,
|vwx|≤ & vx≠ϵ such that uvi wxi y ∉ L for all i=0,1,2,3…

Case 1: String vwx is within an

Let v=aj, x=ak where j+k>=1 and |vwx|<=n.
Ic, z= an bn cn

uvwx y
For i=2, z=uv2wx2y ϵ L
ic, z =an+j+k bn cn
but since an+j+k bn cn ≠ϵ L, our assumption is wrong. Thus, given language is not
Context-free.

Case 2: String vwx is within bn

Similarly we can prove with oth
Let v=bj, x=bk where j+k>=1 and |vwx|<=n.
Ic, z= an bn cn

u vwx y

Department of CSE, EPCET 2025-26 13

TOC(BCS503) Module 4 Notes

For i=2, z=uv2wx2y ϵ L

ic, z = an bn+j+k cn
but since an bn+j+k cn ≠ϵ L, our assumption is wrong. Thus, given language is not
Context-free.
(Note: More examples refer class work)

Closure Properties of CFLs:

CFLs are closed under:

1. Substitution
2. Union, concatenation and star closure
3. Reverse
4. Homomorphism and inverse homomorphism

CFLs are not closed under

1. Intersection
2. Complement

Department of CSE, EPCET 2025-26 14

TOC(BCS503) Module 4 Notes

CFLs are under Union, Concatenation and Star-closure:

Union
Let L1 and L2 be two context free languages. Then we can prove that L1 ∪ L2 is
also context free.

Example
Let L1 = { anbn , n > 0}. Corresponding grammar G1 will have P: S1 → aAb|ab
Let L2 = { cmdm , m ≥ 0}. Corresponding grammar G2 will have P: S2 → cBb| ε
Union of L1 and L2, L = L1 ∪ L2 = { anbn } ∪ { cmdm }
The corresponding grammar G will have the additional production S → S1 | S2.
Thus, CFLs are closed under Union.

Department of CSE, EPCET 2025-26 15

TOC(BCS503) Module 4 Notes

Concatenation:
If L1 and L2 are context free languages, then L1L2 is also context free.
Example
Union of the languages L1 and L2, L = L1L2 = { anbncmdm }
The corresponding grammar G will have the additional production S → S1 S2
Thus, CFLs are closed under concatenation.

Kleene Star or star closure:

If L is a context free language, then L* is also context free.
Example
Let L = { anbn , n ≥ 0}. Corresponding grammar G will have P: S → aAb| ε
Kleene Star L1 = { anbn }*
The corresponding grammar G1 will have additional productions S1 → SS1 | ε.
Thus, CFLs are closed under star closure.

CFLs are closed under Reversal:

CFLs are closed under Homomorphism:

Let L be a CFL with grammar G. Let h be a homomorphism on the terminal
symbols of G.
We can construct a grammar for h(L) by replacing each terminal symbol a by
h(a).
Example:

Department of CSE, EPCET 2025-26 16

TOC(BCS503) Module 4 Notes

G has a production S→0S1 |01

h is defined by h(0)=ab, h(1)= ε
h(L(G)) has the grammar with productions S→abS | ab.
Thus, CFLs are closed under homomorphism.

CFLs are closed under Inverse homomorphism:

Department of CSE, EPCET 2025-26 17

TOC(BCS503) Module 4 Notes

Department of CSE, EPCET 2025-26 18

TOC(BCS503) Module 4 Notes

CFLs are not closed under intersection:

Let us prove this with example grammars. Already we know that,
L={ anbncn :n>=1} is not context free.

However, the following two languages are context-free.

Department of CSE, EPCET 2025-26 19

TOC(BCS503) Module 4 Notes

CFLs are not closed under complement:

Theorem: If L is context free, it is not for complement.

Thus, CFLs are not closed under complement.

Theorem: If L is a CFL and R is a regular language, then L Ո R is a CFL.

Department of CSE, EPCET 2025-26 20

TOC(BCS503) Module 4 Notes

Department of CSE, EPCET 2025-26 21