Q.1 Which of the following problems is decidable?
Halting problem
Membership problem for DFA
Post Correspondence Problem
Equivalence problem for CFGs
Explanation - The membership problem for DFA can be solved by simulating the DFA on the input string, which is a finite process. The other problems listed are undecidable.
Correct answer is: Membership problem for DFA
Q.2 The Halting problem is:
Decidable
Undecidable
Regular
Context-free
Explanation - The Halting problem was proven by Alan Turing to be undecidable; no general algorithm can decide it for all programs and inputs.
Correct answer is: Undecidable
Q.3 Which machine model is most closely associated with the study of decidability?
Finite Automata
Pushdown Automata
Turing Machine
Linear Bounded Automata
Explanation - Decidability is defined in the context of Turing machines because they capture the full power of algorithmic computation.
Correct answer is: Turing Machine
Q.4 The problem of determining if a DFA accepts at least one string is:
Undecidable
Decidable
NP-hard
Co-NP-complete
Explanation - We can check for emptiness of DFA language by searching for reachable accepting states, which is a finite procedure.
Correct answer is: Decidable
Q.5 Which of the following is an undecidable problem?
Emptiness problem for DFA
Halting problem
Membership problem for DFA
Equivalence of DFA
Explanation - While DFA problems are decidable, the Halting problem for Turing machines is undecidable.
Correct answer is: Halting problem
Q.6 Post Correspondence Problem (PCP) is:
Decidable
Undecidable
Regular
Context-free
Explanation - PCP is a classic undecidable problem, meaning there is no general algorithm that solves all instances.
Correct answer is: Undecidable
Q.7 Which of the following problems is decidable for CFGs?
Ambiguity problem
Emptiness problem
Equivalence problem
Universality problem
Explanation - The emptiness problem for CFGs can be decided by checking for reachable terminal derivations.
Correct answer is: Emptiness problem
Q.8 Rice’s theorem states:
Every non-trivial property of Turing machine languages is undecidable
All DFA problems are decidable
CFG ambiguity problem is decidable
Halting problem is decidable
Explanation - Rice’s theorem formalizes that all non-trivial properties of recursively enumerable languages are undecidable.
Correct answer is: Every non-trivial property of Turing machine languages is undecidable
Q.9 Which of the following is a decidable problem for Turing machines?
Halting problem
Acceptance problem
Membership in regular language
Equivalence of Turing machines
Explanation - Membership in regular languages can be decided efficiently using DFA or regex simulation.
Correct answer is: Membership in regular language
Q.10 The class of problems for which there exists a Turing machine that always halts is:
Undecidable problems
Decidable problems
NP problems
Recursive enumerable problems
Explanation - A decidable problem means that a Turing machine always halts with a yes/no answer.
Correct answer is: Decidable problems
Q.11 Which problem is semi-decidable but not decidable?
Halting problem
Emptiness problem for DFA
Membership problem for DFA
Universality problem for DFA
Explanation - The Halting problem is recursively enumerable but not decidable, meaning we can recognize halting cases but not always non-halting ones.
Correct answer is: Halting problem
Q.12 The universality problem for DFA (whether DFA accepts all strings) is:
Decidable
Undecidable
NP-complete
Semi-decidable
Explanation - Universality for DFA can be decided by checking if the complement DFA accepts no string.
Correct answer is: Decidable
Q.13 A language is called decidable if:
It is accepted by a DFA
It is accepted by a PDA
It is accepted by a halting Turing machine
It is context-free
Explanation - A decidable language is one for which a Turing machine always halts and gives a yes/no answer.
Correct answer is: It is accepted by a halting Turing machine
Q.14 Which problem is undecidable for CFGs?
Emptiness problem
Membership problem
Ambiguity problem
Reachability problem
Explanation - Determining whether a CFG is ambiguous is undecidable.
Correct answer is: Ambiguity problem
Q.15 A recursively enumerable language is:
Accepted by a PDA
Accepted by a halting Turing machine
Accepted by a Turing machine that may not halt on all inputs
Always decidable
Explanation - Recursively enumerable languages are those recognized by Turing machines, which may loop indefinitely on some inputs.
Correct answer is: Accepted by a Turing machine that may not halt on all inputs
Q.16 The complement of a recursively enumerable language is always:
Recursively enumerable
Decidable
Undecidable
Not necessarily recursively enumerable
Explanation - The complement of an RE language may or may not be RE unless the language is decidable.
Correct answer is: Not necessarily recursively enumerable
Q.17 Which class of problems includes all decidable languages?
Recursive
RE
NP
PSPACE
Explanation - Decidable languages are also called recursive languages.
Correct answer is: Recursive
Q.18 Which problem is undecidable even though it looks simple?
Halting problem
Emptiness problem for DFA
Membership problem for DFA
Equivalence problem for DFA
Explanation - Despite appearing simple, the Halting problem is undecidable for general Turing machines.
Correct answer is: Halting problem
Q.19 The set of all Turing machine descriptions that accept empty language is:
Decidable
Undecidable
Regular
Context-free
Explanation - Checking whether a Turing machine accepts an empty language is undecidable.
Correct answer is: Undecidable
Q.20 If both a language and its complement are RE, then the language is:
Undecidable
Recursive
Context-free
Regular
Explanation - If both a language and its complement are RE, then both are decidable, so the language is recursive.
Correct answer is: Recursive
Q.21 Which is true about decidable problems?
All problems are decidable
There are undecidable problems
Decidability equals NP-completeness
They cannot be solved by algorithms
Explanation - There exist many undecidable problems such as the Halting problem.
Correct answer is: There are undecidable problems
Q.22 Equivalence of two DFAs is:
Undecidable
Decidable
Semi-decidable
Co-RE
Explanation - Equivalence of DFAs can be decided by constructing DFA for the symmetric difference and testing emptiness.
Correct answer is: Decidable
Q.23 Which of the following is true?
All context-free problems are decidable
Some CFG problems are undecidable
All CFG problems are undecidable
All regular problems are undecidable
Explanation - For CFGs, membership is decidable but problems like ambiguity and equivalence are undecidable.
Correct answer is: Some CFG problems are undecidable
Q.24 Which is an example of a non-trivial property of Turing machines?
Whether it has more than 2 states
Whether it halts on all inputs
Whether input length is prime
Whether alphabet is binary
Explanation - Rice’s theorem applies to semantic properties such as halting, not syntactic ones like alphabet size.
Correct answer is: Whether it halts on all inputs
Q.25 The set of all decidable problems is:
Closed under union, intersection, complement
Closed under union but not complement
Not closed under complement
Closed only under intersection
Explanation - Decidable problems are closed under standard set operations including complement.
Correct answer is: Closed under union, intersection, complement