Pushdown Automata

Question

Among Deterministic pushdown automata and Non deterministic pushdown automata, which is more powerful and why ?

Comments

Non deterministic pushdown automata > Deterministic pushdown automata in terms of acceptance power.

We cannot construct DPDA for WW w belongs to (a+b)+ but NPDA can be done

---

@Hemanth_13 How can we construct NPDA for WW, w$\epsilon$ (a+b)⁺ . As far as I know it's a CSL.

---

@shamim

We can define power of DPDA and NPDA in terms of languages accepted by a Push down automata. DPDA accepts proper subset of CFLs where as NPDA can accept all CFLs. This makes NPDA more powerful compare to DPDA.

---

@swapnil

It's ww^r even length palindromes

Answer 1

In DPDAs, only one move is possible when reading any input from any state but, in NPDAs, there can be multiple moves possible for an input symbol from a state.

In Deterministic Push Down Automata it is always defined that at for a particular input it will be going to a specific state but in case of Non-deterministic Push Down Automata for a specific input it may go to different states ...

So ,  NPDAs are more powerful than DPDAs.

There are Context Free Languages, such as the language of palindromes, that can be accepted by NPDAs but not by DPDAs.

Answer 2

First of all we know about the term "Power" it refers to language accepted.
Every DPDA can be NPDA but every NPDA can't be DPDA, bcz NPDA can accept more languages compared to DPDA, So NPDA is more powerful than DPDA.