Deterministic pushdown automaton

From Wikipedia, the free encyclopedia

In automata theory, a deterministic pushdown automaton is a deterministic finite automata that can make use of a stack containing data. The term "pushdown" refers to the stack operation that inserts data, "push", which pushes down the stack because insert operations can only occur at the top. The term "deterministic pushdown automata" (DPDA) currently refers to abstract computing devices that recognize deterministic context-free languages.

The deterministic pushdown automaton is a deterministic version of the pushdown automaton. Interestingly, deterministic pushdown automata are a proper subset of pushdown automata, unlike deterministic finite automata and nondeterministic finite automata, which are equivalent (as demonstrated by the subset construction).[1]

Contents

[edit] Formal Definition

A PDA M can be defined as a 7-tuple:

M=(Q\,, \Sigma\,, \Gamma\,, q_0\,, Z_0\,, A\,, \delta\,)

where

  • Q\, is a finite set of states
  • \Sigma\, is a finite set of input symbols
  • \Gamma\, is a finite set of stack symbols
  • q_0\,\in Q\, is the start state
  • Z_0\,\in\Gamma\, is the starting stack symbol
  • A\,\subseteq Q\,, where A is the set of accepting states
  • \delta\, is a transition function, where
\delta\,:(Q\, \times ( \Sigma\, \cup \left \{ \lambda\, \right \} ) \times \Gamma\,) \longrightarrow 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 \delta(q,a,x)\, has at most one element.
  • For any q \in Q, x \in \Gamma, if \delta(q, \lambda, x) \not= \emptyset\,, then \delta\left( q,a,x \right) = \emptyset 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.

[edit] Properties

Geraud Senizergues (1998) proved that the equivalence problem for deterministic PDA (i.e. given two deterministic PDA A and B, is L(A)=L(B)?) is decidable. The same problem for nondeterministic PDA is undecidable.

[edit] References

  1. ^ Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing, 102. ISBN 0-534-94728-X. 

[edit] Further reading

  • Hamburger, Henry; Dana Richards (2002). Logic and Language Models for Computer Science. Upper Saddle River, NJ 07458: Prentice Hall, 284-331. ISBN 0-13-065487-6. 
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
n/a Tree-adjoining etc. (Mildly context-sensitive) Embedded pushdown
Type-2 Context-free Context-free Nondeterministic pushdown
n/a Deterministic context-free Deterministic context-free Deterministic pushdown
Type-3 Regular Regular Finite
n/a Star-free Counter-Free
Each category of languages or grammars is a proper subset of the category directly above it,
and any automaton in each category has an equivalent automaton in the category directly above it.