UGC NET CSE | June 2019 | Part 2 | Question: 76

Question

Match $\text{List-I}$ with $\text{List-II}$ :

where $L_1:$ Regular language

           $L_2:$ Context-free language

           $L_3:$ Recursive language

           $L_4:$ Recursively enumerable language

$\begin{array}{clcl} {}& \text{List-I} & {} & \text{List-II} \\  \text{(a)} & \overline{L_3} \cup L_4 & \text{(i)} & \text{Context-free language} \\  \text{(b)} & \overline{L_2} \cup L_3 & \text{(ii)} & \text{Recursively enumerable language} \\ \text{(c)}  & L_{1}^{\ast} \cap L_2 & \text{(iii)} & \text{Recursive Language} \\  \end{array}$

Choose the correct option from those given below :

• A. $\text{(a)-(ii); (b)-(i); (c)-(iii)}$
• B. $\text{(a)-(ii); (b)-(iii); (c)-(i)}$
• C. $\text{(a)-(iii); (b)-(i); (c)-(ii)}$
• D. $\text{(a)-(i); (b)-(ii); (c)-(iii)}$

Answer 1

Before solving such problem we need to know some important point :

context-free language is not closed under intersection, difference and complement.

recursive language is not closed under substitution and homomorphism.

recursive enumerable language is not closed under difference and complement.

For Reference: 1) https://gatecse.in/closure-property-of-language-families/ 

                          2) https://gateoverflow.in/6370/complement-contet-language-recursive-recursive-enumerable

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

for option a) complement of recursive language is recursive which is union by REL which gives REL.

for option b)  complement of CFL is REC language (see the link 2) 

                       which is union by REC, REC is closed under union so result is REC.

for option c)  Kleen closure of REG language is REG,intersection with CFL gives CFL.

option 2 is correct.