GATE GATE Theory of Computation 2 — Questions and Answers
Question 1: The halting problem is:
- Decidable for all Turing machines
- Decidable only for deterministic Turing machines
- Undecidable in general (Correct answer)
- Decidable if the input is a regular language
Correct answer: Undecidable in general
Turing proved that no general algorithm can determine whether an arbitrary Turing machine will halt on a given input.
Question 2: Which of the following closure properties holds for regular languages but NOT for context-free languages?
- Union
- Concatenation
- Kleene star
- Intersection (Correct answer)
Correct answer: Intersection
Regular languages are closed under intersection, but context-free languages are not — the intersection of two CFLs need not be context-free.
Question 3: In a deterministic finite automaton (DFA), what happens when the input string ends in a non-accepting state?
- The DFA loops back to the start state
- The string is rejected (Correct answer)
- The DFA generates an error
- The string is accepted with a warning
Correct answer: The string is rejected
A DFA rejects an input string if, after consuming all input, the machine is in a non-accepting (non-final) state.
Question 4: Which normal form ensures that a context-free grammar has no unit productions and no ε-productions (except possibly S → ε)?
- Greibach Normal Form (GNF)
- Chomsky Normal Form (CNF) (Correct answer)
- Backus-Naur Form
- Wirth Syntax Notation
Correct answer: Chomsky Normal Form (CNF)
Chomsky Normal Form requires all productions to be of the form A → BC or A → a, eliminating unit productions and ε-productions.
Question 5: Which of the following is a decidable problem for context-free grammars?
- Equivalence of two CFGs
- Ambiguity of a CFG
- Membership: does string w belong to L(G)? (Correct answer)
- Intersection of two CFLs being context-free
Correct answer: Membership: does string w belong to L(G)?
The membership problem for CFLs — whether a given string belongs to the language of a given grammar — is decidable using CYK or Earley parsing.
Question 6: A language is Turing-recognizable (recursively enumerable) but NOT decidable. This means:
- A Turing machine always halts and rejects strings not in the language
- A Turing machine may loop forever on strings not in the language (Correct answer)
- No Turing machine can accept strings in the language
- The language is finite
Correct answer: A Turing machine may loop forever on strings not in the language
For a Turing-recognizable but undecidable language, a TM accepts strings in the language but may run forever (loop) on strings not in it.
GATE GATE Theory of Computation 2
The halting problem is: