8,554 views
33 votes
33 votes

Consider the languages:

$L_1 = \left\{ a^nb^nc^m \mid n,m >0\right\}$  and $ L_2 = \left\{a^nb^mc^m\mid n, m > 0\right\}$

Which one of the following statements is FALSE?

  1. $L_1 \cap L_2$ is a context-free language

  2. $L_1 \cup L_2$ is a context-free language

  3. $L_1 \text{ and } L_2$ are context-free languages

  4. $L_1 \cap L_2$ is a context sensitive language

6 Answers

Best answer
38 votes
38 votes

$L_1$ is CFL   [ put $a$'s in stack , and pop $a$ with each $b$]]

$L_2$ is CFL   [put $b$'s in stack and pop $b$ with each $c$ ]

C) is True.

B) is True. CFL is closed under Union    [ $S \rightarrow S_1 \mid S_2$    where $S_1$ is grammar for $L_1$ and $S_2$ for $L_2$]

CFL is not closed under Intersection, so intersection of two CFLs may or may not be CFL. Lets examine:

$L_1 \cap L_2  = \{ a^ib^ic^i ,  i>0 \}$ which is Context sensitive but not context free [can't match $a$'s,$b$'s and $c$'s with one stack]

So, A) is False.

D) is True.

edited by
5 votes
5 votes
A. CFL's are not closed under intersection.
3 votes
3 votes

Clearly A is false, I have solved this by taking example.

L1 union L2 is regular, so it is also CFL, CSL, RE etc.

L1 intersection L2 is CSL

1 votes
1 votes
Answer Option A]

counter example of A= since m and n can be greater than 0 so it is possible case that they can be equal i.e. m=n in this case we can not  construct pda bcz it is not cfl therefore A is false
Answer:

Related questions

50 votes
50 votes
6 answers
2