GATE CS 1992 Q02 — Regular Expressions and Finite Automata

We need to determine for which machine models a non-deterministic machine ($M_1$) always has an equivalent deterministic machine ($M_2$) that recognizes the same language.

1. Non-deterministic Finite Automata (NFA): Every NFA can be converted into an equivalent Deterministic Finite Automaton (DFA) using the subset construction method. Thus, NFAs and DFAs recognize the same class of languages (Regular Languages).
   (Statement is TRUE)
2. Non-deterministic Pushdown Automata (NPDA): NPDAs are strictly more powerful than Deterministic Pushdown Automata (DPDA). For example, the language of even palindromes $L = \{ww^R \mid w \in \{a, b\}^*\}$ is accepted by an NPDA but cannot be accepted by any DPDA.
   (Statement is FALSE)
3. Non-deterministic Turing Machines (NTM): Every NTM can be simulated by a Deterministic Turing Machine (DTM) (e.g., by performing a breadth-first search on the computation tree of the NTM). Thus, NTMs and DTMs recognize the same class of languages (Recursively Enumerable Languages).
   (Statement is TRUE)
4. Option D: Since the statement is true for both finite automata and Turing machines, this option is incorrect.

Hence, the statement is true for cases A and C.