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)

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)

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)

Stack automata

Can somebody please add to this short description of stack automata, with the name of the languages it accepts. Is it equivalent to Turing? Would be good to have its own stand-alone description, and an entry in the general pages on different automata theory models.DBSand (talk) 20:01, 16 June 2012 (UTC)

Complement Proof

Why is it "tricky" to prove closure under complement? If you have a DPDA under the convention that the stack doesn't have to be empty to accept, you can just switch the accept and reject states to create a new DPDA recognizing the complement of the language. Hiiiiiiiiiiiiiiiiiiiii (talk) 19:13, 7 April 2013 (UTC)

As the article mentions, DPDA with empty stack and DPDA with final states are not equivalent. --Zahnradzacken (talk) 20:17, 11 April 2013 (UTC)

Definition of deterministic context-free language

Nowhere in the page is the concept of deterministic context-free language defined. Supposedly a DCFL is one accepted by a DPDA, but there are two different acceptance criteria, and you never mention which one is used. Can you provide a complete definition of "the language accepted by a DPDA"? Yuval Filmus (talk) 21:44, 16 September 2016 (UTC)