Undecidability in Compiler Design MCQs December 19, 2025December 14, 2024 by u930973931_answers 10 min Score: 0 Attempted: 0/10 Subscribe 1. What does “undecidability” in compiler design refer to? (A) The existence of problems that cannot be solved by any algorithm (B) The inability to implement a compiler (C) Errors in source code (D) Inefficiency in parsing algorithms 2. Which of the following is a classic example of an undecidable problem in computation? (A) The Halting Problem (B) Checking if a string belongs to a regular language (C) Evaluating arithmetic expressions (D) Lexical analysis 3. In the context of compilers, which task is affected by undecidability? (A) Lexical analysis (B) Syntax parsing (C) Determining if a program will terminate for all inputs (D) Token generation 4. Rice’s Theorem states that: (A) Any non-trivial semantic property of programs is undecidable (B) All languages are decidable (C) All syntax errors can be detected automatically (D) Every regular expression can be converted to a DFA 5. Which of the following is an undecidable problem for context-free languages? (A) Checking membership of a string (B) Detecting left recursion (C) Generating a parse tree (D) Determining equivalence of two context-free grammars 6. Why is the Halting Problem relevant to compiler design? (A) It helps optimize code generation (B) It simplifies lexical analysis (C) It proves that certain program analyses, like checking for infinite loops, are impossible in general (D) It is used for syntax checking 7. Which of the following tasks can be solved algorithmically despite undecidability in general? (A) Detecting all infinite loops in a program (B) Detecting some syntactic or restricted semantic errors (C) Checking if a Turing machine halts on all inputs (D) Determining program equivalence for all programs 8. What is the significance of undecidability in static program analysis? (A) It allows compilers to optimize programs fully (B) It limits what can be proven automatically about program behavior (C) It eliminates all runtime errors (D) It ensures all type errors can be detected 9. Which problem is decidable despite general undecidability issues? (A) Halting problem (B) Program equivalence for Turing-complete languages (C) Determining if a regular expression matches a string (D) Checking for all infinite loops in a program 10. What approach do compilers use to handle undecidable problems in program analysis? (A) Use heuristics, approximations, or conservative analysis (B) Ignore the problem completely (C) Guarantee perfect detection of all semantic errors (D) Halt compilation whenever undecidability is encountered