The Gateway to Computer Science Excellence
0 votes
135 views
Among Deterministic pushdown automata and Non deterministic pushdown automata, which is more powerful and why ?
in Theory of Computation by Active (2.5k points) | 135 views
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
0

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

0
@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.
0
@swapnil

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.

by Active (3k points)
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.
by Active (1.7k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,251 answers
198,050 comments
104,677 users