GATE CS 1994 Q1.16 — Regular Expressions and Finite Automata

To determine which conversion is not algorithmically possible, let us analyze each option:

• Option A: Regular grammar to context-free grammar
  Every regular grammar is already a context-free grammar (since the production rules of a regular grammar satisfy the constraints of a context-free grammar). Thus, this conversion is trivial and always possible.
• Option B: Non-deterministic FSA to deterministic FSA
  Using the standard subset construction (powerset construction) algorithm, any Non-deterministic Finite Automaton (NFA) can be converted into an equivalent Deterministic Finite Automaton (DFA).
• Option C: Non-deterministic PDA to deterministic PDA
  Non-deterministic Pushdown Automata (NPDA) recognize the class of Context-Free Languages (CFLs), whereas Deterministic Pushdown Automata (DPDA) recognize the class of Deterministic Context-Free Languages (DCFLs). Since $\text{DCFL} \subsetneq \text{CFL}$ (for example, the language $L = \{w w^R \mid w \in \{a,b\}^*\}$ is a CFL but not a DCFL), it is impossible to convert an arbitrary NPDA to an equivalent DPDA.
• Option D: Non-deterministic Turing machine to deterministic Turing machine
  Every Non-deterministic Turing Machine (NTM) can be simulated by a Deterministic Turing Machine (DTM) (e.g., by performing a breadth-first search of the NTM's computation tree). Thus, NTMs and DTMs have equivalent expressive power.

Therefore, the conversion from a non-deterministic PDA to a deterministic PDA is not possible.