Closure Properties of
Context-Free Languages
Osama Awwad
Department of Computer Science
Western Michigan University
September 16, 2016
Closure properties of CFL
Closure properties consider operations on CFL
that are guaranteed to produce a CFL
The CFLs are closed under substitution, union,
concatenation, closure (star), reversal,
homomorphism and inverse homomorphism.
CFLs are not closed under intersection (but the
intersection of a CFL and a regular language is
always a CFL), complementation, and setdifference.
2
Substitution
Each symbol in the strings of one language is replaced by
an entire CFL language
Useful in proving some other closure properties of CFL
Example: S(0) = {anbn| n 1}, S(1) = {aa, bb} is a
substitution on alphabet ={0, 1}.
Substitution
Theorem: If a substitution s assigns a CFL to every symbol in the alphabet
of a CFL L, then s(L) is a CFL.
Proof
Let G = (V, , P, S) be grammar for L
Let Ga= (Va, Ta, Pa, Sa) be the grammar for each a with VVa
=
G= (V, T, P, S) for s(L) where
V = V Va
T = union of Ta for all a
P consists of
All productions in any Pa for a
In productions of P, each terminal a is replaced by Sa
A detailed proof that this construction works is in the reader.
Intuition: this replacement allows anystring in La to take the place
of any occurrence of a in any string of L.
Example (1)
L = {0n1n| n 1}, generated by the grammar
S0S1|01,
s(0) = {anbm|m n}, generated by the grammar SaSb|A;
AaA| ab,
s(1)={ab, abc}, generated by the grammar S abA, A c
|
Rename second and third Ss to S0 and S1 respectively.
Rename second A to B. Resulting grammars are:
S0S1 | 01
S0aS0b | A; AaA | ab
S1abB; Bc |
5
Example(1) Contd...
In the first grammar replace 0 by S0 and 1 by
S1. The combined grammar:
G = ({S, S0, S1, A, B}, {a, b}, P, S),
where P = {S S0SS1 | S0S1, S0 aS0b | A, A
aA | ab, S1abB, B c | }
Application of Substitution
Closure under union of CFLs L1 and L2
Closure under concatenation of CFLs L1 and L2
Closure under Kleenes star (closure * and positive
closure +) of CFLs L1
Closure under homomorphism of CFL Li for every
ai
Union
Use L= {a, b}, s(a) = L1 and s(b)=L2.s(L)= L1L2
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 = P1 P2 { S S1 | S2 }
Example:
L1 = { anbn | n 0 } , L2 = { bnan | n 0 }
G1 : S1 aS1b | , G2 : S2 bS2a |
L1 L2 is G = ({S1, S2 , S}, {a, b}, P, S) where P = {P1 P2
{S S1 | S2 }}
8
Concatenation
Let L={ab}, s(a)=L1 and s(b)=L2. Then s(L)=L1L2
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 = P 1 P 2 { S S1 S 2 }
Example:
L1 = { anbn | n 0 } with G1: S1 aS1b |
L2 = { bnan | n 0 } with G2 : S2 bS2a |
L1L2 = { anb{n+m}am | n, m 0 } with G = ({S, S1, S2}, {a, b}, {S
S1S2, S1 aS1b | , S2 bS2a}, S)
9
Kleenes star
Use L={a}* or L={a}+, s(a)=L1. Then s(L)=L1*
(or s(L)=L1+).
Example:
L1 = {anbn | n 0} (L1)*= { a{n1}b{n1} ... a{nk}b{nk} | k 0 and ni
0 for all i }
L2 = { a{n2} | n 1 }, (L2)*= a*
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 | }
10
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 .
11
Reversal
The CFLs 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 AR
Example:
L = { anbn | n 0 } with P : S aSb |
LR = {bnan | n 0 } with PR : S bSa |
12
Intersection
The CFLs are not closed under intersection
Example:
L = {0n1n2n|n 1} is not context-free.
L1 = {0n1n2i |n 1,i 1 }, L2 = {0i1n2n |n 1,i 1 }
are CFLs 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 CFLs is not CFL
13
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
14
Intersection with RL Proof
P=(QP, , , P, qP, Z0, FP) be PDA to accept CFL by final
state
A=(QA, , A, qA, FA) be a DFA for RL
Construct PDA P = (Q, , , , qo, Z0, F) where
Q = Qp X QA
qo= (qp, qA)
F = (FP X FA)
is in the form ((q, p), a, X) = ((r, s), ) such that
1.
2.
s = A(p, a)
(r, ) is in P(q, a, X)
15
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.
The moves ((qp, qA), w, Z) |-*P ((q, p), , ) are
possible iff (qp, w, Z) |-*P (q, , ) moves and p
= *(qA, w) transitions are possible.
16
Set Difference with RL
For a CFLs 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 of Regular Language is regular
Intersection of a CFL and a regular language is CFL
17
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 isnt
necessarily a CFL.
Contradiction!
18
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 CFLs are not closed under complementation
19
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 CFLs are closed under inverse
homomorphism.
Theorem: If L is a CFL and h is a
homomorphism, then h-1(L) is a CFL
20
Inverse homomorphism proof
Buffer
h(a)
a
Input
Accept/
Reject
PDA
Stack
21
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.
22
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
23
Proof Contd...
is defined by
((q, ), a, X) = {((q, h(a)),a,X)}
If (q, b, X) = {(p, )} where bT or b = then ((q, bx), ,
X) = {((p, x), )}
The start state of P is (q0, )
The accepting state of P is (q, ), where q is an accepting
state of P.
(q0,h(w),Z0)|-*P (p,,) iff ((q0,),w,Z0) |-*P ((p, ), , )
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))
24
Q&A
Thank You
25
