TOC

Question

Suppose L1 and L2 are two language over ∑*

$L=\sum ^{*}-\left ( \left ( \sum ^{*}-L1 \right ) \cup \left ( \sum ^{*}-L2 \right ) \right )$

L1 and L2 are CFL .Which of the following statement is true ?

1.L is necessarily CFL

2.L may or may not CFL

3.L⊆L1

 

(a) only 2                                      (b) 1 and 3

(c)2 and 3                                     (d) All are correct

Answer 1

L=(L1' U L2')'

By demorgan's law..

L= L1 ∩ L2

Since CFL's are not closed under intersection.Therefore L may or may not be CFL.

And by inclusion of intersection we know that ,if A and B are two sets then A ∩ B is a subset of A as well as B .Therefore

L is a subset of L1 as well as L2.

Hence 2 and 3 are correct

Therefore option C.

Comments

I think it's Correct ans

Answer 2

Answer C)

Say,

L₁ ={a^mbⁿ | m=n}

L₂ ={a^mbⁿ | m!=n}

∑^* - L₁ =L₂

∑^* - L₂ =L₁

Now, L₁ U L₂ = ∑*

∑* - ∑* =∅

So, it can be regular

Comments

@Srestha , I have a doubt on 3rd... As we know CFL is not closed under complement , So, It may be CFL or may not be CFL.. assume(on going for a particular case) , CFL' = CSL... So, (CSL U CSL)' = (CSL)' = CSL...

So, L=CSL and L1=CFL... So here CSL is not a subset of CFL.. So , accordind to me, 3rd should be wrong... Please Clear my doubt..

---

yes , but before giving the answer u have to be determined that not even a single case possible in it, then only ur case is correct. But I proved that exception , where the case possible

---

So ,  3rd option is a possibility ... It is not always true ,right ?? So , In this question answer should be (a) or not ?