$III)$ True . All three are here CFL

but I donot know, how they are push poping in $II)$

Dark Mode

517 views

3 votes

select the correct statement

- Non-CFL is closed under reversal operation .
- L=$ \{ \;0^n1^m0^m: n+m \; mod \;6 =2 \} $ is CFL but not regular.
- 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

–1

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

@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