edited by
794 views
3 votes
3 votes

select the correct statement 

  1. Non-CFL is closed under reversal operation .
  2. L=$ \{ \;0^n1^m0^m: n+m \; mod \;6 =2 \} $ is CFL but not regular.
  3. if L is context free and R and S are regular ,then MAJORITY(L,R,S)={ w| w is in atleast two of R,L,S } is also context free

(a) only i      (b) only I and II      (c) Only II and III      (d) All

 

edited by

1 Answer

Best answer
5 votes
5 votes

Answer : D


Statement 1 : Non-CFL is closed under reversal operation .

It's True. 

Proof : 

We can prove it by Contradiction. 

We know that "Set of all CFL languages is closed under Reversal Operation." (Refer link below)

Let $L$ be a Non-CFL. And Let's assume Set Non-CFL of all Non-CFL languages is Not Closed under Reversal Operation (i.e. Reversal of a Non-CFL is Not Necessarily Non-CFL... It could be CFL also.). And let $L$ is such a Non-CFL  that $L^R$ is CFL. 

Since $L^R$ is CFL, $(L^R)^R$ has to be CFL. But $(L^R)^R = L,$ which has to be CFL, which contradicts our assumption. 

Hence, Set Non-CFL of all Non-CFL languages is indeed Closed under Reversal Operation.

https://cs.stackexchange.com/questions/6992/context-free-languages-closed-under-reversal


Statement 2 : $L = \left \{ 0^n1^m0^m | (n+m) \,\,mod\,6=2 \right \}$

Hint : Language $L$ can be seen as Intersection of Two Languages. i.e. $L = L_1 \cap L_2$ where

$L_1 = \left \{ 0^n1^m0^m | n,m \geq 0 \right \}$ 

$L_2 = \left \{ 0^i1^j0^k | (i+j) \,\,mod\,6=2; i,j,k \geq 0 \right \}$

Now, It's easy to see that $L_1$ is CFL whereas $L_2$ is Regular. And Intersection of a CFL and a Regular is Necessarily a CFL. (Refer link below)

Hence, $L$ is CFL (Moreover it is DCFL because $L_1$ is DCFL and Intersection of DCFL and Regular is also DCFL.)

https://www.cs.ucsb.edu/~cappello/136/lectures/17cfls/slides.pdf


Statement 3 : if $L$ is context free and $R$ and $S$ are regular ,then $MAJORITY(L,R,S)=$ {$ w| \,w\,\,\, is\,\,\, in\,\,\, atleast\,\,\, two\,\,\, of\,\,\, R,L,S$ } is also context free.

This One is Pretty simple. If $w$ belongs to at least two of $R,L,S$ then It means It will definitely be in one of the following language : $R \cap L$, $R \cap S$, $L \cap S$

Hence, $Majority(L,R,S) =  (R \cap L) \cup (R \cap S) \cup (L \cap S)$

And Since Intersection/Union of a CFL and a regular is CFL. And Regular set is closed under Intersection. 

$Majority(L,R,S)$ will be CFL. 

https://www.cs.ucsb.edu/~cappello/136/lectures/17cfls/slides.pdf

https://courses.engr.illinois.edu/cs373/fa2013/Lectures/lec08.pdf

selected by

Related questions

2 votes
2 votes
2 answers
4