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:

There are 5 questions to complete.