GATE CSE 2016 Set 2 | Question: 18

Question

Consider the following types of languages: $L_{1}$: Regular, $L_{2}$: Context-free, $L_{3}$: Recursive, $L_{4}$: Recursively enumerable. Which of the following is/are TRUE ?

1. $\overline{L_{3}} \cup L_{4}$ is recursively enumerable.
2. $\overline{L_{2}} \cup L_{3}$ is recursive.
3. $L^{*} _{1} \cap L_{2}$ is context-free.
4. $L_{1} \cup \overline{L_{2}}$ is context-free.

• A. I only.
• B. I and III only.
• C. I and IV only.
• D. I, II and III only.

Comments

option D is the correct answer

Answer 1

1. I. $\overline{L_3} \cup L_4$
   $L_3$ is recursive, so $\overline{L_3}$ is also recursive (closed under complement), 
   So, $\overline{L_3}$ is recursive enumerable.
   $L_4$ is recursive enumerable, 
   so, $\overline{L_3} \cup L_4$ is also recursive enumerable (closed under union). 
    
2. $\overline{L_2} \cup L_3$
   $L_2$ is Context-free, so $\overline{L_2}$, may or may not be Context-free (not closed under complement), but definitely $\overline{L_2}$ is Recursive. 
   $L_3$ is recursive.
   so $\overline{L_2} \cup L_3$ is also recursive (closed under union). 
    
3. $L_1^* \cap L_2$
   $L_1$ is Regular, so $L_1^*$ is also regular (closed under kleene star)
   $L_2$ is Context-free
   so, $L_1^* \cap L_2$ is also context-free (closed under intersection with regular).
    
4. $L_1 \cup \overline{L_2}$
   $L_1$ is regular.
   $L_2$ is context-free, so $\overline{L_2}$ may or may not be Context-free (not closed under complement).
   so, $L_1 \cup \overline{L_2}$ may or may not be Context-free.

Here, answer is D.

Comments

how to know  the union or intersection of two diffrent  type of language will be which type

---

jtushar

Yes it is necessary to go up, and above REL we have Non REL class of languages

---

In that way every cfl also REL , how it will satisfy option b then

Answer 2

may be it will correct 

Comments

https://gateoverflow.in/?qa=blob&qa_blobid=8929616163903734815

---

Firstly, properties 1 and 2 hold, but for property 3-> Regular - AnyLANG = AnyLANG, let AnyLANG=A,

-> Put A=CFL, $Regular \ \cap \ \bar{A}$ . CFL is not closed under complementation so it may or may not be CFL and so  Regular - CFL may or may not be CFL rt?

-> Put A=RE(Recursively Enumerable), $Regular \ \cap \ \bar{A}$ . RE is not closed under complementation so it may or may not be RE and so  Regular - RE may or may not be RE rt?

I mean it is not holding always.

---

@manish_dt actually following property is valid:

for L=REG/DCFL/CFL/CSL/REC/RE:

    1) L U REG = L        
    2) L ∩ REG =L
    3) L - REG =L
    4) L / REG =L

 

the one which you have used is not a valid property, it may not always be true.