MODULE-4
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 ABC or Aa, 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 simplications, which are
themselves useful in various ways.
1. We must eliminate useless symbols, those variables or terminals that do
not appear in any derivation of a terminal string from the start symbol.
2. We must eliminateϵ-productions, those of the formAϵ for some variable
A.
3. We must eliminate unit productions, those of the form AB for variables
A and B.
1. Eliminating Useless Symbols:
are reachable.
2. Eliminatingϵ-Productions:
Nullable Variable: A variable A is nullable if, A=>ϵ
Eliminating Unit Productions:
“A unit production is a production of the form AB, where both A and B
are variables.
However, unit productions can complicate certain proofs and they also introduce
extra steps into derivations that technically need not be there.
Ex:AB
B->a|ab
Can be rewritten as, Aa|ab, by eliminating the unit production AB.
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
Step1:
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
Step2:
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
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:
Every non empty CFL without ϵ has a grammar G in which all productions are
in one of the two simple forms, either:
1. ABC, where A,B, and C, are each variable, or
2. Aa, 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
Arrangeallthebodiesoflength2ormoreconsistonlyvariables.
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.
SABa
Aaab
BAc
Ans:
Step1: Eliminate ϵ-productions:
Given grammar doesn’t have any ϵ-productions.
Step2:Eliminate unit productions
Given grammar doesn’t have any unit productions.
Step3:Eliminate useless symbols
Given grammar doesn’t have any useless symbols.
Step4:Convert to CNF
SABTa SAD1
D1BTa
ATaTaTb ATaD2
D2TaTb
BATc BATc
Taa Taa
Tbb Tbb
Tcc Tcc
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’={SAD1
D1BTaA
TaD2D2Ta
Tb
BATcTa
a Tbb
Tcc}
(Note:ForMoreproblemsreferclasswork)
The Pumping Lemma for Context-Free Languages:
The Size of Parse Trees:
Statement of the Pumping Lemma for CFL:
Proof:
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 in to substrings u, v, w, x and y such
that z=uvwxy where,
|vwx|≤&vx≠ϵ
3. Find any I such that uviwxiy∉L. According to pumping lemma,
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 Lis
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 in to uvwxy such that,
|vwx|≤&vx≠ϵ such that uviw xiy∉L for all i=0,1,2,3…
Case1:String vwx is within an
Let v=aj, x=ak where j+k>=1and|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+kbncn ≠ϵL, our assumption is wrong. Thus, given language is not
Context-free.
Case2:String vwx is within bn
Similarly we can prove with o th
Letv=bj,x=bkwherej+k>=1and|vwx|<=n. Ic, z=
an bn cn
u vwx y
For i=2,z=uv2wx2yϵL
ic, z=anbn+j+kcn
but since anbn+j+kcn ≠ϵ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
CFLs are under Union, Concatenation and Star-closure:
Union
[Link] we can prove that L1∪ L2is also
context free.
Example
Let L1 = { anbn , n >0}. Corresponding grammar G1 will have P: S1 → aAb|ab
LetL2={cmdm,m≥0}.CorrespondinggrammarG2willhaveP:S2→cBb|ε Union of L1
and L2, L= L1∪ L2 = { anbn } ∪ { cmdm }
The corresponding grammar G will have the additional productionS→S1|S2.
Thus, CFLs are closed under Union.
Concatenation:
If L1 and L2 are context free languages, then L1 ,L2is also context free.
Example
Union of the languages L1andL2,L=L1L2={anbncmdm}
The corresponding grammar G will have the additional production S→S1S2
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 G1will 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:
G has a productionS0S1|01
h is defined by h(0)=ab, h(1)=ε
h(L(G))has the grammar with productions
SabS|ab. Thus, CFLs are closed under homomorphism.
CFLs are closed under Inverse homomorphism:
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.
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.