Deterministic pushdown automaton

From Wikipedia, the free encyclopedia

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,Σ,Γ, q 0, Z 0, 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
$q 0$ is the start state, an element of $Q$
$Z 0$ 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"

Categories: Automata theory | Computational models

Deterministic pushdown automaton

From Wikipedia, the free encyclopedia

[edit] Definition

Views

Navigation

interaction

Search

In other languages