Use the languages L1 = { a^i b^i c^j d^j | i, j 0 } and L2 = { a^j b^i c^i d^k |
ID: 3815721 • Letter: U
Question
Use the languages L1 = { a^i b^i c^j d^j | i, j 0 } and L2 = { a^j b^i c^i d^k | i, j, k 0 } to show that the class of context-free languages is not closed under intersection. Construct your counterexample as follows:
a. First, show that both L1 and L2 are CFLs.
b. Express L = L1 L2 in set notation, and give a brief justification that the set L, as you have expressed it, is in fact the intersection of L1 and L2 . About two or three sentences should be enough. Be sure to justify both directions: (i) L1 L2 L and (ii) L L1 L2 .
c. Show that L = L1 L2 is not a CFL.
d. Finally, use parts (a) and (c) to conclude that the class of CFLs is not closed under intersection.
Explanation / Answer
a. Given L1 = { a^i b^i c^j d^j | i, j 0 }
L2 = { a^j b^i c^i d^k | i, j, k 0 }
We can construct Context free grammar for the languase L1 as follows :
G1: S->AB
A->aAb|
B->cBd|
Here S gives AB and non terminal A gives the half part of the language L1 i.e a^i b^i means equal number of a's and b's.
We can construct Context free grammar for the languase L2 as follows :
G2: S->aS|AB
A->bAc|
B->dB|
Since there exist Context free grammar for the language L1 and L2 both.
Therefore Language L1 and L2 are Context free languages generated by grammars G1 and G2 respectively.
b. L = L1 L2 in set notation as follows:
L= { , abcd, aabbccdd , aaabbbcccddd , aaaabbbbccccdddd , ..........}
i.e L = { a^i b^i c^i d^ : i >=0 }
In the first language L1 , the same number of a's and b's and same number of cs and ds
In the second language L2, same number of b's and c's
So , in intersection set of L1 and L2 means in L , all the words that have the same number of a's,b's,c's, and d's.
c. Here L ={ a^i b^i c^i d^ : i >=0 } is not context free language.
Explanation : We can not construct a PDA for the language L beacause single stack is not sufficient for it. We can also prove it by using Pumping Lemma for Context free languages.
Pumping Lemma for CFL :
Let L be a CFL. Then there exists a constant
p such that if z is any string in L where |z| p, then we can write z = uvwxy subject to the following
conditions: 1. |vwx| £ p. This says the middle portion is not larger than p.
2. vx . We’ll pump v and x. One may be empty, but both may not be empty.
3. For all i 0, uv i wx i y is also in L. That is, we pump both v and x.
d. Since L1 and L2 is Context free languages but their intersection L is not Context free. It means intersection of two Context free languages not necessarly Context free.
We can say that Context free languages are not closed under intersection.