UGC NET CSE | June 2005 | Part 2 | Question: 1

Question

Which of the following is not true ?

• A. Power of deterministic automata is equivalent to power of non-deterministic automata
• B. Power of deterministic pushdown automata is equivalent to power of non-deterministic pushdown automata
• C. Power of deterministic turing machine is equivalent to power of non-deterministic turing machine
• D. All the above

Answer 1

Answer:

B. Power of deterministic pushdown automata is equivalent to power of non-deterministic pushdown automata.

The above statement is incorrect.

Answer 2

Option B is correct here.

PDA is by default NPDA and the expressive power of NPDA is more than DPDA. NPDA accept more number of language than DPDA. so they are not equivalent.

Please refer here:

1. GATE 2009.
2. GATE 1994
3. GATE 2011