Difference between revisions of "Deterministic pushdown automata"
From Wiki @ Karl Jones dot com
Karl Jones (Talk | contribs) (Created page with "In automata theory, a '''deterministic pushdown automaton''' (DPDA or DPA) is a variation of the pushdown automaton. == Description == The class of deterministic pus...") |
Karl Jones (Talk | contribs) |
||
| Line 20: | Line 20: | ||
* [https://en.wikipedia.org/wiki/Deterministic_pushdown_automaton Deterministic pushdown automata] @ Wikipedia | * [https://en.wikipedia.org/wiki/Deterministic_pushdown_automaton Deterministic pushdown automata] @ Wikipedia | ||
| − | [[Category: | + | [[Category:Computer science]] |
Latest revision as of 15:46, 24 September 2016
In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton.
Description
The class of deterministic pushdown automata accepts the deterministic context-free languages, a proper subset of context-free languages.
Machine transitions are based on the current state and input symbol, and also the current topmost symbol of the stack. Symbols lower in the stack are not visible and have no immediate effect. Machine actions include pushing, popping, or replacing the stack top.
A deterministic pushdown automaton has at most one legal transition for the same combination of input symbol, state, and top stack symbol. This is where it differs from the nondeterministic pushdown automaton.
See also
External links
- Deterministic pushdown automata @ Wikipedia
