Test by Bikram | Theory of Computation | Test 2 | Question: 1

Question

Choose the appropriate context-free language $L_2$ that ensure that $L_1 \cap  L_2$ is NOT context-free, where $L_1 = \{x^ny^m z^m \mid m > 0, n  > 0 \}$:

• A. $L_2 = \{x^n y^n z^{2m}  \mid n > 0, m > 0 \}$
• B. $L_2 = \{x^n y^m z^p  \mid n > m \text{ and } m > p \}$
• C. $L_2 = \{x^n y^n z^n \mid n > 0 \}$
• D. Both (A) and (B)

Comments

@Nitesh, No DCFL is not closed under intersection, they are closed under complementation. 

You can check the table here. 

---

Thanks sorry i got wrong

---

Anyone can help me with the PDA of option A. I’m only able to count it till a^nb^n how to count z^2m ??

Answer 1

L1 = {xⁿ y^m z^m / m > 0, n  > 0 } . Here in L1, the number of y and z are equal.

Option A.
L2 = {xⁿ yⁿ z^2m  / n > 0, m > 0 } . Here the number of x and y are equal.

L1 $\cap$ L2 = {$x^{n} y^{n} z^{n}$  / n > 0}. This is context sensitive language, not CFL. As L1 is saying the number of y and z are equal and L2 is saying that the number of x and y are equal. Hence All of them are equal.

Option B.
L2 = {xⁿ y^m z^p  / n > m and m > p }. Here the number of y is more than z. But in L1 all the string have the number of y and z equal. So their intersection is $\Phi$. This is a regular language.  Hence CFL too.

Option C.
L2 = {xⁿ yⁿ zⁿ / n > 0}. Here L2 is not context free. In question it is asking for CFL.

Only, option A is correct.

Comments

Option B) Is this language CFL or CSL?

---

It's not CFL