GATE 2013 CS (CS1) – Question 27
Which are false? 1: Every nondeterministic TM has an equivalent deterministic TM. 2: TM-recognizable languages are closed under union and complement. 3: Decidable languages are closed under intersection and complement. 4: Recognizable languages are closed under union and intersection.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) 2 only
Explanation
A deterministic TM can simulate a nondeterministic one by dovetailing, so 1 is true. Recognizable languages are union/intersection closed but not complement-closed, making 2 false and 4 true. Decidable languages are intersection/complement closed, so 3 is true. Only statement two is false, C.