NIELIT 2022 April Scientist B | Section B | Question: 43

Question

Consider the following types of languages:

$\text{L1}:$ Regular,

$\text{L2}:$ Context-free,

$\text{L3}:$ Recursive,

$\text{L4}:$ Recursively enumerable.

Which of the following is/are $\text{TRUE}$ ?

1. $\text{L3}’ \cup \text{L4}$ is recursively enumerable
2. $\text{L2} \cup \text{L3}$ is recursive
3. $\text{L1}^{\ast} \cup \text{L2}$ is context-free
4. $\text{L1} \cup \text{L2}’$ is context-free

• A. $\text{I}$ only
• B. $\text{I}$ and $\text{III}$ only
• C. $\text{I}$ and $\text{IV}$ only
• D. $\text{I, II}$ and $\text{III}$ only

Answer 1

 Answer: D

1. Recursive languages are closed under complementation hence $L_3’$ is recursive, and recursively enumerable too, and REL is also closed under union. So, 
   $L_3’  \cup L_4 $ is recursively enumerable.
    
2. $L_2$ is CFL hence recursive too and recursive is closed under union. Therefore,
   $L_2 \cup L_3$ is recursive.
    
3. $L_1$ is regular language and it is closed under kleen star operation, hence $L_1^*$ is regular hence CFL too, and CFL is closed under union operation. So,
   $L_1^*$ $\cup$ $L_2$ is CFL.
    
4. CFL are not closed under complementation. Therefore $L_2’$ may or may not be CFL but every CFL is also CSL and CSL is closed under complementation. So, $L_1 \cup L_2’$ is CSL (may or may not be CFL).
   
   Refer: https://gatecse.in/closure-property-of-language-families/

Comments

Reasoning for IV is not correct. What if $L_2 = \{\},$ which is a CFL?

---

Yes sir, you are right. CFL is not closed under complementation hence it may or may not be CFL but CFL is also CSL and CSL is closed under complementation so $L1 \cup L2’$ is CSL.
Is this correct @Arjun sir?

---

Counter example ,

L1={${\varepsilon }$}…...………….....…..(Regular)

L2=complement of the language {${ww | w \in (a+b)^{+} }$}…..………..….(CFL)

$\bar{L2}=\left \{ ww| w\in (a+b)^{+} \right \}$…....……….….(CSL)

$L1 \bigcup \bar{L2}=\left \{{\epsilon } \right \}\bigcup \left \{ ww |w\in (a+b)^{+}\right \}$.………...(CSL)