4,327 views
2 votes
2 votes
Which one is more powerful Deterministic push down automata or Non Deterministic push down automata ?

3 Answers

Best answer
7 votes
7 votes
NPDA(Non Deterministic Push Down Automata) is more powerful than DPDA(Deterministic Push Down Automata).

for eg: There are languages for which we can make NPDA but DPDA can not be possible...

L = { WW^r   | W belongs to (a + b)^(+) }
selected by
4 votes
4 votes
expressive power of DPDA < expressive power of NPDA

ie. language accpeted by deterministic PDA is greater then Non deterministic PDA

therefore NPDA is more powerful then DPDA
2 votes
2 votes
non deterministic push down automata is more powerfull

Related questions

0 votes
0 votes
2 answers
2
Alakhator asked Nov 11, 2018
870 views
Construct a PDA for set of strings over {a,b,c,d} such thatL={ a^i b^j c^k d^l / i=k or j=l , i,j,k,l >=1}
0 votes
0 votes
1 answer
3
Abhisek Tiwari 4 asked Nov 6, 2018
703 views
Consider Ldf set all languages accepted by DPDA by final state,Lef set of all languages accepted by DPDA by Empty stack ThenA)Ldf proper subset of Lef.B)Ldf = Lef.C)Lef ...