L34- ToC

Closure Properties of CFL

Course Instructors:
Div 1: Praveen Pawar (Div 1)
Div 2: Jibi Abraham (Div 2)

1
 Closure properties of CFL
 Closure properties consider operations on CFL that
are guaranteed to produce a CFL
 The CFL’s are closed under substitution, union,
concatenation, star closure, reversal,
homomorphism and inverse homomorphism
 CFL’s are not closed under intersection,
complementation and set-difference
 But, a CFL closed with a regular language for
 Intersection
 set-difference
 The result of operation is a CFL
 Substitution
 Each symbol in the strings of one language is
replaced by an entire CFL language
 Theorem: If a substitution s assigns a CFL to every
symbol in the alphabet of a CFL L, then s(L) is a
CFL
 Substitution Proof
 Proof
 Let G = (V, , P, S) be grammar for L
 Let Ga= (Va, Ta, Pa, Sa) be the grammar for each a  
with VVa=
 G= (V, T, P, S) for s(L) where
 V = V  Va

 T = union of Ta all for a 

 P consists of

 All productions in any Pa for a  

 In productions of P, each terminal a is replaced

by Sa
 Substitution Example-1
 L = {0n1n| n 1},
 generated by the CFG: S0S1|01
 s(0) = {anbm| m n},
 generated by the CFG: S0aS0b|A; AaA| ab
 s(1)={ab, abc},
 generated by the CFG: S1  abB, B  c |
 Example-1 Contd...
 S0S1|01
 S0aS0b|A; AaA| ab
 S1  abB; B  c |
 In the first grammar replace 0 by S0 and 1 by S1
 The combined grammar:
SS0SS1 | S0S1
S0aS0b | A; AaA | ab
S1abB; Bc | 
 Application of Substitution
 Closure under union of CFL’s L1 and L2
 Closure under concatenation of CFL’s L1 and L2
 Closure under Kleene’s star (closure * and positive
closure +) of CFL’s L1
 Closure under homomorphism of CFL Li for every
ai 
 Union
 Use L= {a, b}, s(a) = L1 and s(b)=L2
 s(L)= L1L2
 Example:
 L1 = { anbn | n  0 } , L2 = { bnan | n  0 }
 G1 : S1  aS1b | , G2 : S2  bS2a | 
 To get grammar for L1  L2 ?
 Add new start symbol S and rules S  S1|S2
 We get grammar G = (V, T, P, S) where
V = V1  V2  { S }, where S  V1  V2
P = P 1  P2  { S  S1 | S 2 }
 Concatenation
 Let L={ab}, s(a)=L1 and s(b)=L2. Then s(L)=L1L2
 Example:
 L1 = { anbn | n  0 } , L2 = { bnan | n  0 }
 L1L2 = { anb{n+m}am | n, m  0 }
 To get grammar for L1L2 ?
 Add new start symbol and rule S  S1S2
 We get G = (V, T, P, S) where
V = V1  V2  { S }, where S  V1  V2
P = P1  P2  { S  S1S2 }
 Kleene’s star
 Use L={a}*, s(a)=L1. Then s(L)=L1*
 Example:
 L1 = {anbn | n  0} generated by S1  aS1b | 
 (L1)*= { a{n1}b{n1} ... a{nk}b{nk} | k  0 and ni  0 for all i }
 To get grammar for (L1)* ?
 Add new start symbol S and rules S  SS1 | 
 We get G = (V, T, P, S) where
V = V1  { S }, where S  V1
P = P1  { S  SS1 | }
 Polling
 Say true or false?
 If L1 = {anbn | n  0}
generated by S1  aS1b | ,
then L1* is generated by the grammar with
productions:
 S  SS1 | 
 S1  aS1b | 
a) True
b) False

11
 Homomorphism
 Closure under homomorphism of CFL L for every
a
 Suppose L is a CFL over alphabet  and h is a
homomorphism on .
 Let s be a substitution that replaces every a  , by
h(a). ie s(a) = {h(a)}
 Then h(L) = s(L)
 h(L) ={h(a1)…h(ak) | k  0} where h(ak) is a
homomorphism for every ak  
 Inverse homomorphism
 To recall: If h is a homomorphism, and L is any
language, then h-1(L), called an inverse
homomorphism, is the set of all strings w such that
h(w)L
 The CFL’s are closed under inverse
homomorphism.
 Inverse homomorphism – Proof
 Theorem: If L is a CFL and h is a homomorphism,
then h-1(L) is a CFL
 Proof Contd...
 After input a is read, h(a) is placed in a buffer
 Symbols of h(a) are used one at a time and
fed to PDA being simulated
 Only when the buffer is empty does the PDA
read another of its input symbol and apply
homomorphism to it
 Proof Contd...
 Suppose h applies to symbols of alphabet Σ and
produces strings in T*
 Let PDA P = (Q, T, Γ, δ, q0, Z0, F) that accept CFL
L by final state
 Construct a new PDA P = (Q, Σ, Γ, δ, (q0, ), Z0,
(F x )) to simulate language of h-1(L), where
 Q is the set of pairs (q, x) such that

 q is a state in Q
 x is a suffix of some string h(a) for some input string

a in Σ
 Proof Contd...
 δ is defined by
 δ((q, ), a, X) = {((q, h(a)), a, X)}
 If δ(q, b, X) = {(p, )} where bT or b =  then δ((q, bX), , X) = {((p,
X), )}
 Start state of P is (q0, )
 Accepting state of P is (q, ), where q is an accepting state
of P
 (q0, h(w), Z0)|-*P (q, , ) iff ((q0, ), w, Z0) |-*P ((q, ), , )
 P accepts h(w) if and only if P accepts w, because of the
way the accepting states of P are defined
 Thus L(P) = h-1(L(P))
 Reversal
 The CFL’s are closed under reversal
 This means then if L is a CFL, so LR is a CFL
 It is enough to reverse each production of a CFL
for L, i.e., substitute A by AR
 Example: L = {anbn | n  0}. The CFG for the
language is having the productions: S  aSb | .
 Then LR is generated by the grammar with
productions: S  bSa | , which defines the
language: LR = {bnan | n  0}
 Intersection
 The CFL’s are not closed under intersection
 Example:
 L = {0n1n2n | n  1 } is not context-free
 L1 = {0n1n2i | n  1, i  1}, and L2 = {0i1n2n | n  1, i 
1} are CFL’s with corresponding grammars for L1:
SAB; A0A1 | 01; B2B | 2 , and for L2: S AB;
A0A | 0; B1B2 | 12.
 However, L = L1  L2
 Thus intersection of CFL’s is not CFL
 Complementation
 LC is not necessarily a CFL
 Proof:
 Assume that CFLs were closed under complement
 If L is a CFL then LC is a CFL
 Since CFLs are closed under union, L1C L2C is a
CFL
 And by our assumption (L1C L2C) C is a CFL
 But, (L1C L2C) C = L1 L2 which we just showed
isn’t necessarily a CFL
 Contradiction!
 Set Difference
 L1 and L2 are CFLs. L1 - L2 is not
necessarily a CFL
Proof:
 L1 = * - L
 * is regular and is also CFL
 But * - L = LC
 If CFLs were closed under set difference, then * - L
= LC would always be a CFL
 But CFL’s are not closed under complementation
 Intersection with RL
 Theorem: If L is CFL and R is a regular language,
then L  R is a CFL

Accept/
FA
AND Reject

PDA

Stack
 Intersection with RL Proof
 P=(QP, , , P, qP, Z0, FP) be PDA to accept CFL by
final state
 A=(QA, , A, qA, FA) for DFA for RL
 Construct PDA P = (Q, , , , qo, Z0, F) where
 Q = QpXQA
 qo= (qp, qA)
 F = (FPX FA)
  is in the form ((q, p), a, X) = ((r, s), ) such that
1. s = A(p, a)
2. (r, ) is in P(q, a, X)
 Proof Contd…
 For each move of PDA P, we make the same move
in PDA P and also we carry along the state of DFA
A in a second component of P
 P accepts a string w iff both P and A accept w
 w is in L  R
 Moves ((qp, qA), w, Z) |-*P ((q, p), , ) are
possible iff
 (qp, w, Z) |-*P (q, , ) moves and p = *(qA, w)
transitions are possible
 Polling
 L1 = {anbn | n  0},
 L2 = {anbmck | n, m, k  1} then L1  L2 is
a) CFL but not Regular Language
b) CFL and Regular Language
c) Non-CFL and non-Regular Language

25
 Set Difference with RL
 For a CFL’s L, and a regular language R,
L - R is a CFL
Proof:
 R is regular and RC is also regular
 L - R = L  RC
 Complement of a Regular Language is regular
 Intersection of a CFL and a regular language is CFL
27