GATE CS 2011 Q.8 (CS Q.8): Context-Free Grammars, Pushdown Automata and CFLs

Which of the following pairs have DIFFERENT expressive power?

Deterministic finite automata (DFA) and Non-deterministic finite automata (NFA)

Deterministic push down automata (DPDA) and Non-deterministic push down automata (NPDA)

Deterministic single-tape Turing machine and Non-deterministic single-tape Turing machine

Single-tape Turing machine and multi-tape Turing machine

Official answer and solution

Solution

Recall the expressive power and equivalence of deterministic and non-deterministic automata across Chomsky hierarchy levels.

For finite automata: Every NFA can be converted to an equivalent DFA via the subset construction, so DFA and NFA have identical expressive power (they recognize regular languages).

For Turing machines: Non-deterministic single-tape TMs and multi-tape TMs can all be simulated by a deterministic single-tape TM with polynomial slowdown, so they all recognize exactly the recursively enumerable languages.

For pushdown automata: DPDA recognizes Deterministic Context-Free Languages (DCFL), whereas NPDA recognizes all Context-Free Languages (CFL). Because languages such as the language of even-length palindromes $L = \{w w^R \mid w \in \{a,b\}^*\}$ are CFL but not DCFL, DPDA and NPDA possess strictly different expressive power.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.