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 a new top symbol to the stack. A deterministic pushdown automaton is effectively a particular type of pushdown automaton, namely ones that have 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 PDA M can be defined as a 7-tuple:

where

• is a finite set of states
• is a finite set of input symbols
• is a finite set of stack symbols
• is the start state
• is the starting stack symbol
• , where A is the set of accepting states
• is a transition function, where

and λ denotes the empty string.

M is deterministic if it satisfies both the following conditions:

• For any , the set has at most one element.
• For any , if , then for every

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.

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 under union. To prove that the complement of a deterministic PDA is again 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 (2001) proved that the equivalence problem for deterministic PDA (i.e. given two deterministic PDA A and B, is L(A)=L(B)?) is decidable. 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. 

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.