retagged by
745 views
4 votes
4 votes

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 \}$:

  1. $L_2 = \{x^n y^n z^{2m}  \mid n > 0, m > 0 \}$
  2. $L_2 = \{x^n y^m z^p  \mid n > m \text{ and } m > p \}$
  3. $L_2 = \{x^n y^n z^n \mid n > 0 \}$
  4. Both (A) and (B)
retagged by

1 Answer

Best answer
16 votes
16 votes

L1 = {xn ym zm / m > 0, n  > 0 } . Here in L1, the number of y and z are equal.

Option A.
L2 = {xn yn z2m  / 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 = {xn ym zp  / 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 = {xn yn zn / n > 0}. Here L2 is not context free. In question it is asking for CFL.

Only, option A is correct.

selected by
Answer:

Related questions

1 votes
1 votes
0 answers
2
4 votes
4 votes
0 answers
4
Bikram asked Aug 12, 2017
607 views
The number of possible finite automata with two states $a0$ and $a1$ (where $a0$ is always the initial state over the alphabet $\{p, q\}$) which accepts empty language is...