in Theory of Computation edited by
517 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

 

in Theory of Computation edited by
517 views

4 Comments

$I)$True. Only DCFL not closed under reversal. So, even NCFL is closed under reverse

$III)$ True . All three are here CFL

but I donot know, how they are push poping in $II)$
–1
–1
srestha can you explain 3rd one
0
0

III) True . All three are here CFL

 @srestha ,That is Not correct logic. If All Three were given CFL (instead of two of them as regular), Answer would be different because CFL set is Not closed under Intersection.  And Majority language is nothing but the Union of $R \cap L, R \cap S, L \cap S.$

0
0

1 Answer

5 votes
5 votes
Best answer

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

2 Comments

edited by
thnxx deepak bhaiya  through this explanation i could understood most of the other things

 

in third statement we can also add

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

these will give CFL only answer would not be changed
0
0

@Deepakk Poonia (Dee) For statement 2, how would an FA be created for L2? Would there be 6 states for the first 0 and then for each of these states, there would be 6 states for 1?

0
0

Related questions