retagged by
11,555 views
41 votes
41 votes

Let $L_1, L_2$ be any two context-free languages and $R$ be any regular language. Then which of the following is/are CORRECT?

  1. $L_1 \cup L_2$ is context-free
  2. $\overline{L_1}$ is context-free
  3. $L_1 - R$ is context-free
  4. $L_1 \cap L_2$ is context-free
  1. I, II and IV only
  2. I and III only
  3. II and IV only
  4. I only
retagged by

6 Answers

Best answer
38 votes
38 votes

Statement I is TRUE as CFGs are closed under union.

Statement II is FALSE as CFGs are not enclosed under complementation.

Statement III is TRUE as $L1−R$ can be written as $L1\cap \overline{R}$. Regular language are closed under complementation and intersection of CFG and Regular is CFG.

Statement IV is FALSE as CFGs are not enclosed under intersection.

So, I and III are correct. Option B.

edited by
19 votes
19 votes
intersection of two CFL are not closed operation, and CFL also not closed under complimentation, 
CFL-reg we can write like this CFL $CFL\cap \bar{regular}$  so regular language closed under complimentation and intersection of CFL with regular is always CFL.
17 votes
17 votes
CFLs are closed under union operation and difference with a regular language.Hence option i and iii are correct.

But CFLs are not closed under intersection and complementation.so option ii and iv are wrong.

Ans:B) i and iii
edited by
7 votes
7 votes

okay CFL s are closed under Union

so  1 is correct

option 2: L1' is not CFL as it is not closed under complementation

option 3 is nothing but intersection with regular language which is CFL

3 is correct so

4 is not correct as cfl is not closed under intersection

so from this i get 1,2,3 correct but that is not in option i think your option 2 will be a different..

so 1 and 3 correct

Answer:

Related questions

77 votes
77 votes
12 answers
3
Arjun asked Feb 14, 2017
28,048 views
Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$-NFA whose transition table is given below:$$\...