edited by
12,026 views
48 votes
48 votes

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.
  1. I only.
  2. I and III only.
  3. I and IV only.
  4. I, II and III only.
edited by

2 Answers

Best answer
118 votes
118 votes
  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.

edited by
3 votes
3 votes

may be it will correct 

Answer:

Related questions

3 votes
3 votes
2 answers
3
1 votes
1 votes
1 answer
4
raviyogi asked Dec 30, 2017
668 views
CFL over a single alphabet are always->A. dcflB. regularC. dcfl but not regulard. non regular