In automata theory, a deterministic pushdown automaton is a deterministic finite state machine that can make use of a stack containing data. The term "pushdown" refers to the "pushing down" action by which the prototypical mechanical automaton would physically contact a punchcard to read its information. The term "deterministic pushdown automata" (DPDA) currently refers to abstract computing devices that recognize deterministic context-free languages. In theoretical computer science, automata theory is the study of abstract machines and problems they are able to solve. ... In the theory of computation, a deterministic finite state machine or deterministic finite automaton (DFA) is a finite state machine where for each pair of state and input symbol there is one and only one transition to a next state. ... Simple representation of a stack In computer science, a stack is a temporary abstract data type and data structure based on the principle of Last In First Out (LIFO). ... The punch card (or Hollerith card) is a recording medium for holding information for use by automated data processing machines. ... This article or section does not cite its references or sources. ...
The deterministic pushdown automaton is a weaker version of the pushdown automaton In automata theory, a pushdown automaton is a finite automaton that can make use of a stack containing data. ...
Definition
A PDA M can be defined as a 7-tuple:
M = (Q,Σ,Γ,q0,Z0,A,δ) where
Q is a finite set of states
Σ is a finite set of the input alphabet
Γ is a finite set of the stack alphabet
q0 is the start state, an element of Q
Z0 is the initial stack symbol, an element of Γ
A is the set of final states, a subset of Q
δ is a finite transition relation the set of finite subsets of
M is deterministic if it satisfies both the following conditions:
For any , the set δ(q,a,X) has at most one element.
For any , if Ø, then δ(q,a,X) =Ø for every
There are two possible acceptance criteria: acceptance by empty stack and acceptance by final state. The two are easily shown to be equivalent: a final state can perform a pop loop to get to an empty stack, and a machine can detect an empty stack and enter a final state by detecting a unique symbol pushed by the initial state.
A linear bounded automaton is a device which is more powerful than a pushdownautomaton but less so than a Turing machine.
For every context-free grammar, there exists a pushdownautomaton such that the language generated by the grammar is identical with the language generated by the automaton.
Context Free Automata and Pushdown Automata, from the University of Birmingham
Pushdown automata are abstract devices defined in automata theory.
Pushdown automata exist in deterministic and non-deterministic varieties, and the two are not equipotent.
If we allow a finite automaton access to two stacks instead of just one, we obtain a device much more powerful than a pushdownautomaton: it is equivalent to a Turing machine.
Feeds |
Contact