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 |

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.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.