Deterministic pushdown automaton


Deterministic pushdown automaton

In automata theory, a pushdown automaton is a finite automaton with an additional stack of symbols; its transitions can take the top symbol on the stack and depend on its value, and they can add new top symbols to the stack. A deterministic pushdown automaton is effectively a particular type of pushdown automaton, namely one that has at most one transition for the same combination of input symbol, state, and top stack symbol. Technically however, the notion of determinism for pushdown automata is more complicated than for finite automata as the transition is determined by both state and top stack symbol. This means that if we omit the stack from a deterministic pushdown automaton we usually end up with a nondeterministic finite automaton.

The term "pushdown" refers to the fact that the stack can be regarded as being "pushed down" like a tray dispenser at a cafeteria, since the operations never work on elements other than the top element. A stack automaton, by contrast, does allow operations on other elements, and stack automata can recognize a strictly larger set of languages than pushdown automata.

A deterministic context-free language is a language recognized by some deterministic pushdown automaton. Not all context-free languages are deterministic.[1] This is unlike the situation for deterministic finite automata, which are also a subset of the nondeterministic finite automata but can recognize the same class of languages (as demonstrated by the subset construction).

Contents

Formal Definition

A (not necessarily deterministic) 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\colon(Q\, \times ( \Sigma\, \cup \left \{ \varepsilon\, \right \} ) \times \Gamma\,) \longrightarrow \mathcal{P}(Q \times \Gamma ^{*})
where Γ * means "a finite list (maybe empty) of elements of Γ", ε denotes the empty string, and \mathcal{P}(X) is the power set of a set X.

M is deterministic if it satisfies both the following conditions:

  • For any q \in Q, a \in \Sigma \cup \left \{ \varepsilon \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, \varepsilon, 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.

Similarly, unlike the nondeterministic pushdown automaton, restricting the deterministic PDA to a single state reduces the class of languages accepted. The LL(1) languages are exactly those which can be recognized by single-state deterministic PDAs [2].

Computation

The formal definition of the computation is the same as that of the pushdown automaton, with the only difference being that there is now only one computation for each input. For an automaton A, L(A) is the set of inputs such that there is a computation from the initial configuration until an accepting one.

Properties

Closure

Closure properties of deterministic context-free languages (accepted by deterministic PDA by final state) are drastically different from the context-free languages. As an example they are (effectively) closed under complementation, but not closed under union. To prove that the complement of a language accepted by a deterministic PDA is also accepted by a deterministic PDA is tricky. In principle one has to avoid infinite computations.

As a consequence of the complementation it is decidable whether a deterministic PDA accepts all words over its input alphabet, by testing its complement for emptiness. This is not possible for context-free grammars (hence not for general PDA).

Equivalence problem

Geraud Senizergues (1997) proved that the equivalence problem for deterministic PDA (i.e. given two deterministic PDA A and B, is L(A)=L(B)?) is decidable.[3] For nondeterministic PDA, equivalence is undecidable.

Notes

  1. ^ Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. p. 102. ISBN 0-534-94728-X. 
  2. ^ Kurki-Suonio, R. (1969). "Notes on top-down languages". BIT 9 (3): 225–238. doi:10.1007/BF01946814.  edit
  3. ^ Sénizergues, Géraud (1997). "The equivalence problem for deterministic pushdown automata is decidable". AUTOMATA, LANGUAGES AND PROGRAMMING 1256/1997: 671–681. doi:10.1007/3-540-63165-8_221. 

References

Further reading

  • Hamburger, Henry; Dana Richards (2002). Logic and Language Models for Computer Science. Upper Saddle River, NJ 07458: Prentice Hall. pp. 284–331. ISBN 0-13-065487-6. 

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Pushdown automaton — In automata theory, a pushdown automaton (PDA) is a finite automaton that can make use of a stack containing data. Operation Pushdown automata differ from normal finite state machines in two ways: # They can use the top of the stack to decide… …   Wikipedia

  • Deterministic context-free language — A deterministic context free language is a formal language which is defined by a deterministic context free grammar.[1] The set of deterministic context free languages is called DCFL[2] and is identical to the set of languages accepted by a… …   Wikipedia

  • Deterministic context-free grammar — In formal grammar theory, the deterministic context free grammars (DCFGs) are a proper subset of the context free grammars. The deterministic context free grammars are those a deterministic pushdown automaton can recognize. A DCFG is the finite… …   Wikipedia

  • Deterministic automaton — is a concept of automata theory in which the outcome of a transition from one state to another given a certain input can be predicted for every occurrence. A common deterministic automaton is a deterministic finite state machine (sometimes… …   Wikipedia

  • Deterministic finite-state machine — An example of a Deterministic Finite Automaton that accepts only binary numbers that are multiples of 3. The state S0 is both the start state and an accept state. In the theory of computation and automata theory, a deterministic finite state… …   Wikipedia

  • Nested stack automaton — In automata theory, a nested stack automaton is a finite automaton that can make use of a stack containing data which can be additional stacks.[1] A nested stack automaton may read its stack, in addition to pushing or popping it. A nested stack… …   Wikipedia

  • Nested word — In computer science, more specifically in automata and formal language theory, nested words are a concept proposed by Alur and Madhusudan as a joint generalization of words, as traditionally used for modelling linearly ordered structures, and of… …   Wikipedia

  • Chomsky hierarchy — Within the field of computer science, specifically in the area of formal languages, the Chomsky hierarchy (occasionally referred to as Chomsky–Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars. This hierarchy of… …   Wikipedia

  • Computation history — In computer science, a computation history is a sequence of steps taken by an abstract machine in the process of computing its result. Computation histories are frequently used in proofs about the capabilities of certain machines, and… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.