edited by
6,384 views
30 votes
30 votes

For any two languages $L_{1}$ and $L_{2}$ such that $L_{1}$ is context-free and $L_{2}$ is recursively enumerable but not recursive, which of the following is/are necessarily true?

  1. $\bar{L}_{1}$ ( Complement of $L_{1}$) is recursive
  2. $\bar{L}_{2}$ ( Complement of $L_{2}$) is recursive
  3. $\bar{L}_{1}$ is context-free
  4. $\bar{L}_{1}$ ∪ $L_{2}$ is recursively enumerable
  1. I only
  2. III only
  3. III and IV only
  4. I and IV only
edited by

2 Answers

Best answer
43 votes
43 votes

Answer is D.

$L_1$ is context-free and hence recursive also. Recursive set being closed under complement, $L_1$' will be recursive.

$L_1$' being recursive it is also recursively enumerable and Recursively Enumerable set is closed under Union. So, $L_1' \cup L_2$ is recursively enumerable.

Context free languages are not closed under complement, so $III$ is false

Recursive set is closed under complement. So, if $L_2$' is recursive, ($L_2$')'  $= L_2$ is also recursive which is not the case here. So, $II$ is also false.

edited by
1 votes
1 votes
The following statement is necessarily true:

L¯1 (Complement of L1) is recursive

The complement of a context-free language is recursive, because a context-free language can be recognized by a non-deterministic pushdown automata (PDA), and the complement of a language recognized by a PDA can be recognized by a deterministic finite automata (DFA), which is a simpler machine.

The following statement is not necessarily true:

L¯2 (Complement of L2) is recursive

The complement of a recursively enumerable but not recursive language may or may not be recursive. If L2 is recursive, then L¯2 is recursive. But if L2 is not recursive, then L¯2 is not recursive.

The following statement is not necessarily true:

L¯1 is context-free

The complement of a context-free language is not necessarily context-free. Since context-free languages can be recognized by pushdown automata, and the complement of context-free languages may not be recognizable by any pushdown automata, it may not be context-free.

The following statement is not necessarily true:

L¯1 ∪ L2 is recursively enumerable

The union of two languages may or may not be recursively enumerable. It depends on the specific languages L1 and L2, and whether or not their union is recursively enumerable can only be determined by analyzing the properties of those specific languages.
Answer:

Related questions

83 votes
83 votes
4 answers
1
makhdoom ghaya asked Feb 13, 2015
23,489 views
Consider the NPDA $$ \left \langle Q= \left \{ q_{0}, q_{1}, q_{2} \right \},\Sigma = \left \{ 0, 1 \right \}, \Gamma = \left \{ 0, 1, \perp \right \}, \delta, q_{0}, \p...
13 votes
13 votes
4 answers
3
makhdoom ghaya asked Feb 11, 2015
7,197 views
Given Set $A= {2, 3, 4, 5}$ and Set $B= { 11, 12, 13, 14, 15}$, two numbers are randomly selected, one from each set. What is the probability that the sum of the two numb...
80 votes
80 votes
7 answers
4
makhdoom ghaya asked Feb 13, 2015
28,737 views
The least number of temporary variables required to create a three-address code in static single assignment form for the expression $q + r / 3 + s - t * 5 + u * v/w$ is_...