Question

Which of the following pairs have DIFFERENT expressive power?
1. Deterministic finite automata (DFA) and Non-deterministic finite automata (NFA)
2. Deterministic push down automata (DPDA) and Non-deterministic push down automata (NPDA)
3. Deterministic single-tape Turing machine and Non-deterministic single-tape Turing machine
4. Single-tape Turing machine and multi-tape Turing machine

Answer 1

Correct Answer - Option 2 : Deterministic push down automata (DPDA) and Non-deterministic push down automata (NPDA)

The correct answer is option 2

Option 1: SAME expressive power

NFA and DFA have the same expressive power.

Option 2: DIFFERENT expressive power

Some languages are accepted by NPDA but not by deterministic PDA. Therefore expressive power of DPDA < expressive power of NPDA.

So, deterministic pushdown automata (DPDA) and non-deterministic pushdown automata (NPDA) have DIFFERENT expressive power

Option 3: SAME expressive power

Deterministic single-tape Turing machine and Non-deterministic single-tape Turing machine have the same expressive power

Option 4: SAME expressive power

Multi-tape Turing machines has same power as single tape Turing machines.