Jump to content

Talk:Deterministic pushdown automaton

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by SineBot (talk | contribs) at 02:33, 1 November 2010 (Signing comment by 96.35.172.252 - "→Nondeterminism vs determinism: new section"). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Deterministic_pushdown_automaton&oldid=394094607"