Talk:Deterministic pushdown automaton

Computer science B‑class High‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science

B

This article has been rated as B-class on Wikipedia's content assessment scale.

High

This article has been rated as High-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

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]

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)[reply]

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)[reply]

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