Talk:Deterministic pushdown automaton

I changed lambda for epsilon as the letter for the empty string, to have the same notation than the "pudhdown automata" page, I also explained what means "\Gamma *" which may be unclear for some people.

Nondeterminism vs determinism

As a new student of the subject, the fact that non-deterministic PDAs are strictly more powerful than deterministic PDAs is suprising and counter-intuitive to me, especially given the the equivalence of machines in the realm of regular languages.

I believe a short explanation of this, or an example language that cannot be accepted by a DPDA would be beneficial. I've had this class at two universities and while we talk about PDAs a lot in both classes, this particular fact was never brought to my attention.

David —Preceding unsigned comment added by 96.35.172.252 (talk) 02:32, 1 November 2010 (UTC)[reply]

Thank you for your question. An example can be found in Deterministic context-free language. Feel free to incorporate it in this article, too. The language of non-trivial even-length palindromes cannot be decided by a DPDA. Although I haven't consulted the citation, I assume it's due to the fact that a PDA can non-deterministically find the middle while for a DPDA there is no way of recognizing whether the current symbol is beyond the middle of the even-length palindrome, i.e. it could never know whether it still should push or whether it should pop the stack. --Zahnradzacken (talk) 19:48, 2 November 2010 (UTC)[reply]

Merge with pushdown automaton article

The commonalities and differences of deterministic and nondeterministic PDAs would be clearer if these two topics were covered in a single article rather than separate articles with different ways of introducing the same ideas.DBSand (talk) 18:02, 16 June 2012 (UTC)[reply]