class Identification

Question

Consider two languages, L₁ and L₂ defined over same alphabet ∑. Let L₁⊕L₂={w|w belongs to exactly one out of L₁ and L₂}. Suppose L₁ is regular and L₂ is context-free, then which of the following statements is true?

1.   L₁⊕L₂ is undecidable
2.  ​​​​​​​ L₁⊕L₂ is context-free but not necessarily regular
3.  ​​​​​​​ L₁⊕L₂ is regular
4.  ​​​​​​​ L₁⊕L₂ is decidable but not necessarily context-free
    

Answer 1

This is a closure property based question ..

We know :

L₁  ⊕  L₂  =   (L₁ - L₂)  ∪  (L₂ - L₁)

(or)           =   (L₁ ∪  L₂)  -  (L₁ ∩ L₂)

Let us use the 2nd definition ..

Let X  =    (L₁ ∪  L₂)  

     Y  =    (L₁ ∩ L₂)

Now given L₁ is regular and L₂  is CFL..So they belong to different levels in Chomsky hierarchy..As we know we should go up the Chomsky as upper class is more general as compared to lower class (in this case upper class is referred to CFL).

So we know that every regular language is also CFL..So now we push L₁ to upper level and now hence X means union of two CFLs..So X is also a CFL as CFLs are closed under union..

Now coming to Y , Y is not a CFL necessarily as CFLs are not closed under intersection..So now we push Y to next upper level which is CSL..As we know CSLs are closed under intersection , hence  L₁  and L₂ being CFL will be CSL also by default..So Y is also going to be a CSL..

Hence X - Y means difference of a CFL  and a CSL..But we know

X -  Y   =   X  ∩  Y'

Now the complement of Y will be also a CSL as CSL is closed under complementation as well..Now X is a CFL and Y' is a CSL ..Hence for X ∩  Y'  we need that X is pushed to next higher level which is CSL..Now X is a CSL and Y is also a CSL..Hence X ∩ Y' will also be a CSL always as CSL is closed under intersection..

Hence X - Y will be a CSL(Context Sensitive Language) definitely..

Hence the stronger answer for the above query will be a CSL..

So the given language is a recursive language as well and hence decidable as :

a) Every lower class language in Chomsky hierarchy is by default higher class language as well..

b) Undecidable language begins from recursively enumerable but not recursive level.

So option A) is false..Also option B) is false as explained earlier..

Also option C) is false as a language is not guaranteed to be a CFL even then we cannot guarantee regularity of the language as well..

So the correct answer to the above question is option D) as the language is guaranteed to be CSL and hence also recursive and hence decidable but may or may not be CFL as explained earlier..

Comments

No. Your example shows that the resulting language is not regular - option 3 can be eliminated. It does not prove result will always be context-free.

---

Thanks! Got it Sir... :D

---

L1 U L2{Regular U Context-free}=Regular,right?

L1 intersection L2{Regular intersection Context-free}=Context-free,right?

Correct me!

Answer 2

$L_1 \oplus L_2$ is not necessarily context-free. This can be proved by giving a counter exmaple. Let

$L_1 = \Sigma^*$

$L_2 = \text{comp}\{ww\mid w \in \Sigma^*\}$

Now,

$L_1 \oplus L_2 = \left(L_1 \cap L_2^c\right) \cup \left(L_1^c \cap L_2\right)$

$= L_2^c \cup \emptyset = {L_2}^c$

And we know $L_2^c$ is not context-free for the given $L_2$. We could also take any context free language here whose complement is not context-free.

Comments

But ww is itself not a CFL..It is a CSL..

---

No. But $L_2$ was not CFL- corrected now.

Answer 3

if any language is regular then according to Chomsky hierarchy it must be context free.. so I think it's 2..

Comments

For TOC, no guess work is good - we should use set theory to prove or give counter example via intuition.

---

yes sir.. got it.. thanku for correcting me how to actually approach these kind of questions...