Deterministic pushdown automaton

From Wikipedia, the free encyclopedia

You have new messages (last change).

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.

The deterministic pushdown automaton is a weaker version of the pushdown automaton

[edit] 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(Q \times ( \Sigma \cup \left \{ \Lambda \right \} ) \times \Gamma) \longrightarrow the set of finite subsets of (Q \times \Gamma ^{*})

M is deterministic if it satisfies both the following conditions:

  • For any q \in Q, a \in \Sigma \cup \left \{ \Lambda \right \}, X \in \Gamma, the set δ(q,a,X) has at most one element.
  • For any q \in Q, X \in \Gamma, if \delta(q, \Lambda, X) \not=Ø, then δ(q,a,X) = Ø for every a \in \Sigma

There are two possible acceptance criteria: acceptance by empty stack and acceptance by final state. The two are not equivalent for the deterministic pushdown automaton (although they are for the non-deterministic pushdown automaton). The languages accepted by empty stack are the languages that are accepted by final state, as well as have no word in the language that is the prefix of another word in the language.

Automata theory: formal languages and formal grammars
Chomsky
hierarchy		 Grammars Languages Minimal
automaton
Type-0 Unrestricted Recursively enumerable Turing machine
n/a (no common name) Recursive Decider
Type-1 Context-sensitive Context-sensitive Linear-bounded
n/a Indexed Indexed Nested stack
Type-2 Context-free Context-free Nondeterministic Pushdown
n/a Deterministic Context-free Deterministic Context-free Deterministic Pushdown
Type-3 Regular Regular Finite
Each category of languages or grammars is a proper subset of the category directly above it.
Retrieved from "http://en.wikipedia.org../../../d/e/t/Deterministic_pushdown_automaton.html"
In other languages