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

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

0 votes

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

0

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

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

0

0 votes

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.