GATE CS 2013 Q17 — Regular and Context-free Languages

Let us analyze each statement individually to determine its truth value:

1. Statement 1: "For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine."
   TRUE. Non-deterministic Turing machines (NTMs) and deterministic Turing machines (DTMs) are equivalent in computational power. Any language recognized by an NTM can also be recognized by a DTM by simulating all computation paths.
2. Statement 2: "Turing recognizable languages are closed under union and complementation."
   FALSE. Turing recognizable (recursively enumerable, or RE) languages are closed under union, but they are not closed under complementation. If they were closed under complementation, then every RE language would also be decidable (since a language $L$ is decidable if and only if both $L$ and its complement $\bar{L}$ are RE), which is a contradiction (e.g., the Halting Problem is RE but its complement is not).
3. Statement 3: "Turing decidable languages are closed under intersection and complementation."
   TRUE. Turing decidable (recursive) languages are closed under all boolean operations, including union, intersection, and complementation.
4. Statement 4: "Turing recognizable languages are closed under union and intersection."
   TRUE. Turing recognizable (RE) languages are closed under both union and intersection.

Since only Statement 2 is FALSE, the correct option is C.