GATE CS 2011 Q8 — Regular Expressions and Finite Automata

To determine which pair has different expressive power, we compare the class of languages recognized by each model in the pair:

1. DFA and NFA: Both recognize the class of Regular Languages. Thus, they have the same expressive power.
2. DPDA and NPDA:
   • DPDA recognizes the class of Deterministic Context-Free Languages (DCFLs).
   • NPDA recognizes the class of Context-Free Languages (CFLs).
   • Since DCFL is a strict subset of CFL (for example, the even-length palindrome language $L = \{ww^R \mid w \in \{a, b\}^*\}$ is a CFL but cannot be recognized by any DPDA), DPDA and NPDA have different expressive power.
3. Deterministic and Non-deterministic single-tape Turing machines: Both recognize the class of Recursively Enumerable (RE) languages. Thus, they have the same expressive power.
4. Single-tape and Multi-tape Turing machines: A multi-tape Turing machine can be simulated by a single-tape Turing machine with a quadratic slowdown, but they both recognize the same class of RE languages. Thus, they have the same expressive power.

Therefore, only the pair in option B has different expressive power.