Log In
0 votes
Among Deterministic pushdown automata and Non deterministic pushdown automata, which is more powerful and why ?
in Theory of Computation 182 views
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.


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.

It's ww^r even length palindromes

2 Answers

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.

0 votes
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.

Related questions

0 votes
0 answers
0 votes
1 answer
2 votes
1 answer
Which is more powerful :- 2-way Non-Deterministic Pushdown Machine(NDPDM) or 2-way Deterministic Pushdown Machine(DPDM) ? (or) Do both machine models have the same power ?
asked Mar 4, 2018 in Theory of Computation ankitgupta.1729 146 views
0 votes
1 answer
Consider Ldf set all languages accepted by DPDA by final state,Lef set of all languages accepted by DPDA by Empty stack Then A)Ldf proper subset of Lef. B)Ldf = Lef. C)Lef proper subset of Ldf. D)None .
asked Nov 6, 2018 in Theory of Computation Abhisek Tiwari 4 176 views