1. Which of the following problems is undecidable in compiler design?
A) Syntax analysis of a given language
B) Determining if a given context-free grammar is ambiguous
C) Performing constant folding optimization
D) Generating intermediate code for a function call
Answer: B) Determining if a given context-free grammar is ambiguous
2. Which of the following is true about undecidability in the context of compiler design?
A) Some problems cannot be solved by any algorithm
B) All problems in compiler design are decidable
C) Undecidable problems can always be approximated by algorithms
D) Compilers can solve all problems with a finite number of steps
Answer: A) Some problems cannot be solved by any algorithm
3. The Halting Problem, which is undecidable, is most closely related to which compiler process?
A) Syntax analysis
B) Semantic analysis
C) Code generation
D) Optimization and dead code elimination
Answer: B) Semantic analysis
4. Which of the following compiler phases involves a problem that is undecidable in certain cases?
A) Lexical analysis
B) Syntax analysis
C) Type checking and type inference
D) Code optimization
Answer: C) Type checking and type inference
5. Why is determining whether a given program will run forever an undecidable problem?
A) It is equivalent to solving the Halting Problem
B) It can be solved using a finite state machine
C) It can always be approximated in a practical setting
D) It is always possible to compute the number of operations in a program
Answer: A) It is equivalent to solving the Halting Problem
6. Which of the following is an example of an undecidable problem that arises in optimization during compiler design?
A) Finding the minimum number of register allocations
B) Identifying unreachable code
C) Determining if a program will terminate or run forever
D) Performing loop unrolling for performance improvement
Answer: C) Determining if a program will terminate or run forever
7. Which of the following undecidable problems arises from the limitations of finite automata in parsing and recognition?
A) Ambiguity detection in context-free grammar
B) Determining whether a context-free grammar can generate all strings of a language
C) Determining whether a context-free grammar generates an infinite language
D) Deciding if a given string belongs to a regular language
Answer: A) Ambiguity detection in context-free grammar
8. Which of the following is undecidable for a compiler when performing code optimization?
A) Constant folding
B) Loop unrolling
C) Dead code elimination
D) Identifying whether code transformations preserve program semantics
Answer: D) Identifying whether code transformations preserve program semantics
9. What is a characteristic of problems that are undecidable in compiler design?
A) They always involve finite state machines
B) They can be solved by algorithms within polynomial time
C) They cannot be solved by any algorithm in a finite number of steps
D) They can always be reduced to simpler problems
Answer: C) They cannot be solved by any algorithm in a finite number of steps
10. Which of the following problems is undecidable in the context of type inference in compilers?
A) Determining whether a program has any type errors
B) Inferring the type of a function based on its usage
C) Ensuring that all variables in a program are assigned types
D) Checking if a type system is consistent and complete
Answer: D) Checking if a type system is consistent and complete
11. Which of the following undecidable problems is related to the static analysis phase of a compiler?
A) Constant propagation
B) Identifying the reachability of code blocks
C) Determining if a program can enter an infinite loop
D) Register allocation for a function
Answer: C) Determining if a program can enter an infinite loop
12. What is the significance of undecidability in compiler design?
A) It means that all compiler phases can be automated
B) It imposes limits on the kinds of optimizations and checks a compiler can perform
C) It guarantees that all programming languages can be compiled efficiently
D) It simplifies the creation of more efficient algorithms for code generation
Answer: B) It imposes limits on the kinds of optimizations and checks a compiler can perform
13. Which problem in compiler design is related to undecidability and can prevent the compiler from determining whether a program will always terminate?
A) Syntax parsing
B) Loop invariant detection
C) Control flow analysis
D) Halting problem
Answer: D) Halting problem
14. Which of the following undecidable problems affects a compiler when trying to check the equivalence of two programs?
A) Type checking
B) Determining if two programs are syntactically equivalent
C) Checking if two programs will always produce the same output for all inputs
D) Identifying common subexpressions
Answer: C) Checking if two programs will always produce the same output for all inputs
15. Which of the following compiler design problems cannot be solved by any algorithm due to undecidability?
A) Detecting whether a program contains syntax errors
B) Identifying unused variables
C) Determining if a program has a semantic error
D) Deciding whether a program will halt for every input
Answer: D) Deciding whether a program will halt for every input