Rice’s theorem MCQs

By: Prof. Dr. Fazal Rehman | Last updated: September 23, 2024

Rice’s Theorem MCQs Rice’s theorem states that any non-trivial property of a language accepted by a Turing machine is: A) Decidable B) Recognizable C) Undecidable D) Context-free Answer: C A non-trivial property of Turing machines means that it holds for: A) All Turing machines B) No Turing machines C) Some Turing machines D) Regular languages Answer: C Which of the following is a consequence of Rice’s theorem? A) Every Turing machine accepts a regular language. B) Every Turing machine halts on every input. C) No algorithm can decide whether a Turing machine accepts a non-trivial property. D) Every Turing machine can be simulated by a finite automaton. Answer: C Rice’s theorem implies that the problem of determining whether a Turing machine has a property that applies to some Turing machines and not to others is: A) Decidable B) Undecidable C) Context-free D) Regular Answer: B The set of all Turing machines that accept the same language forms a: A) Context-free language B) Regular language C) Decidable set D) Non-trivial property Answer: C According to Rice’s theorem, the problem of determining whether a Turing machine accepts a language that contains at least one string is: A) Decidable B) Undecidable C) Context-free D) Regular Answer: B Which of the following is an example of a non-trivial property of Turing machines? A) Having a specific number of states B) Halting on all inputs C) Having a finite tape alphabet D) Having a specific transition function Answer: A The set of Turing machines that accept all strings is: A) Finite B) Decidable C) Context-free D) Not closed under complement Answer: B Rice’s theorem applies to: A) Deterministic finite automata B) Context-free grammars C) Turing machines D) Regular expressions Answer: C A Turing machine that accepts all strings forms a: A) Regular language B) Context-free language C) Decidable set D) Trivial property Answer: D  

• Theory of Automata MCQs
• Finite Automata MCQs
  • Deterministic Finite Automata (DFA) MCQs
  • Non-deterministic Finite Automata (NFA) MCQs
  • Equivalence of DFA and NFA MCQs
  • Minimization of DFA MCQs
• Regular Languages
  • Regular Expression MCQs
  • Properties of regular languages MCQs
  • Closure properties MCQs
  • Pumping Lemma for regular languages MCQs
• Context-Free Grammars (CFG)
  • CFG MCQs
  • Parse trees and derivations MCQs
  • Ambiguity in grammars MCQs
• Pushdown Automata (PDA) MCQs
  • Deterministic PDA vs Non-deterministic PDA MCQs
  • Relationship between PDA and context-free languages MCQs
• Context-Free Languages MCQs
  • Properties of context-free languages MCQs
  • Closure properties MCQs
  • Pumping Lemma for context-free languages MCQs
• Turing Machines MCQs
  • Turing machine as a language recognizer and transducer MCQs
• Decidability and Undecidability MCQs
  • Decidable languages and problems MCQs
  • Undecidable languages and problems MCQs
  • Rice’s theorem MCQs
  • Reduction techniques MCQs
• Computational Complexity MCQs
  • Time complexity classes (P, NP, NP-complete, NP-hard) MCQs
  • Space complexity classes (PSPACE, L, NL) MCQs
  • Polynomial time reductions MCQs
• Advanced Topics in Automata Theory
  • Linear-bounded automata MCQs
  • Context-sensitive grammars and languages MCQs
  • Chomsky hierarchy MCQs
  • Introduction to quantum automata MCQs
• Applications of Automata Theory MCQs