Question 1 |

Which of the following statements is/are TRUE?

**MSQ**Every subset of a recursively enumerable language is recursive. | |

If a language L and its complement \bar{L} are both recursively enumerable, then L must be recursive. | |

Complement of a context-free language must be recursive. | |

If L_1 and L_2 are regular, then L_1 \cap L_2 must be deterministic context-free. |

Question 1 Explanation:

Question 2 |

Let < M > denote an encoding of an automaton M. Suppose that \Sigma =\{0,1\}. Which of the following languages is/are NOT recursive?

L= \{ \langle M \rangle \mid M \text{ is a DFA such that } L(M)=\emptyset \} | |

L= \{ \langle M \rangle \mid M \text{ is a DFA such that } L(M)=\Sigma ^ * \} | |

L= \{ \langle M \rangle \mid M \text{ is a PDA such that } L(M)=\emptyset \} | |

L= \{ \langle M \rangle \mid M \text{ is a PDA such that } L(M)=\Sigma ^ * \} |

Question 2 Explanation:

Question 3 |

The set of all recursively enumerable languages is

closed under complementation | |

closed under intersection. | |

a subset of the set of all recursive languages. | |

an uncountable set |

Question 3 Explanation:

Question 4 |

If L and P are two recursively enumerable languages then they are not closed under

Kleene star L^{*} of L | |

Intersection L \cap P | |

Union L \cup P | |

Set difference |

Question 4 Explanation:

Question 5 |

Given the following statements

S1 : Every context-sensitive language L is recursive

S2 : There exists a recursive language that is not context-sensitive

Which statements are true?

S1 : Every context-sensitive language L is recursive

S2 : There exists a recursive language that is not context-sensitive

Which statements are true?

Only S1 is correct | |

Only S2 is correct | |

Both S1 and S2 are not correct | |

Both S1 and S2 are correct |

Question 5 Explanation:

Question 6 |

If L and \bar L are recursively enumerable then L is

regular | |

context-free | |

context-sensitive | |

recursive |

Question 6 Explanation:

Question 7 |

Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that \bar{Y} reduces to W, and Z reduces to \bar{X} (reduction means the standard many-one-reduction). Which one of the following statements is TRUE?

W can berecursivelyenumerableand Z is recursive. | |

W can berecursiveand Z is recursivelyenumerable | |

W is notrecursivelyenumerableand Z is recursive | |

W is notrecursivelyenumerableand Z is notrecursive. |

Question 7 Explanation:

Question 8 |

Let L be a language and \bar{L} be its complement. Which of the following is NOT a viable possibility?

Neither L nor \bar{L} is recursively enumerable (r.e.). | |

One of L and \bar{L} is r.e. but not recursive; the other is not r.e. | |

Both L and \bar{L} are r.e. but not recursive | |

Both L and \bar{L} are recursive. |

Question 8 Explanation:

Question 9 |

A problem whose language is recursion is called?

Unified problem | |

Boolean function | |

Recursive problem | |

Decidable |

Question 9 Explanation:

Question 10 |

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

L2 - L1 is recursively enumerable | |

L1 - L3 is recursively enumerable | |

L2 \cup L1 is recursively enumerable | |

L2 \cap L1 is recursively enumerable |

Question 10 Explanation:

There are 10 questions to complete.