-
Which of the following statements is/are false?
1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
2. Turing recognisable languages are closed under union and complementation.
3. Turing decidable languages are closed under intersection and complementation.
4. Turing recognisable languages are closed under union and intersection.
-
- 1 and 4 only
- 1 and 3 only
- 2 only
- 3 only
- 1 and 4 only
Correct Option: C
1. Non-deterministic Turing Machine can be simulated by a deterministic Turing Machine with exponential time true.
2. Turing recongnizable language are "not" closed under complementation. For any Turing recognizable language the Turing Machine ' T ' recognizing ' L ' may not terminate on inputs x ∉ L - False
3. Turing decidable languages are CLOSED under union and complementation. It is easy to determine if turing machine is decidable-True So, answer is option (c) only 2.
