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).

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

• G. Sénizergues: L(A)=L(B)? decidability results from complete formal systems. Theoretical Computer Science 251(1-2): 1-166 (2001)
• G. Sénizergues: L(A)=L(B)? A simplified decidability proof. Theoretical Computer Science 281(1-2): 555-608 (2002)

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.