deterministic pushdown automaton (original) (raw)

Formally, a deterministic pushdown automaton, or DPDA for short, is a non-deterministic pushdown automaton M=(Q,Σ,Γ,T,q0,⊥,F) where the transition function T has the following properties: for any p∈Q, a∈Σ, and A∈Γ,

1. 1. T⁢(p,a,A)∪T⁢(p,λ,A) is at most a singleton,
2. 1. T⁢(p,a,A)∩T⁢(p,λ,A)=∅.

The properties can be interpreted as follows: given any configuration of M, if there is a transition to the next configuration, the transition must be unique. The second property just insures that T⁢(p,a,A)≠T⁢(p,λ,A), so that when a λ-transition is possible for a given (p,A), no other transitions are possible for the same (p,A).

The way a DPDA works is exactly the same as an NPDA, with several modes of acceptance: acceptance on final state, acceptance on empty stack, and acceptance on final state and empty stack. However, unlike a NPDA, these acceptance methods are not equivalent. It can be shown that the set ℰ of languages accepted on empty stack is a proper subset of the set ℱ of languages determined on final state. In fact, every language in ℰ is prefix-free, while some languages in ℱ are not.

Some examples: the set of palindromes {u∈Σ*∣u=rev⁡(u)} is unambiguous, but not deterministic. The language {am⁢bn∣m≥n≥0} is deterministic, but not prefix-free, and hence can not be accepted by any DPDA on empty stack. The language {an⁢bn∣n≥0} can be accepted by a DPDA on empty stack, but is not regular.

Any formal grammar that generates a deterministic language is said to be deterministic context-free. A deterministic context-free grammar can be described by what is known as the L⁢R⁢(k) (http://planetmath.org/LRk) grammars.

The family of deterministic languages is closed under complementation, intersection with a regular language, but not arbitrary (finite) intersection, and hence not union.

Remark. The reason why ℰ≠ℱ can be traced back to the definition of a DPDA: it allows for the following possibilities for a DPDA M:

• •
  M completely stops reading an input word because either there are no available transitions from one configuration to the next:
  or the stack is emptied before the last input symbol is read: a configuration (p,u,λ) is reached and u is not empty.
• •
  M consumes the last input symbol, and continues processing because of λ-transitions.

Some authors consider these imperfections of M as being “non-deterministic”, and put additional constraints on M, such as making sure T is a total function, the stack is never empty, and delimiting input strings.

References

• 1 A. Salomaa Computation and Automata, Encyclopedia of Mathematics and Its Applications, Vol. 25. Cambridge (1985).
• 2 S. Ginsburg, The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York (1966).
• 3 D. C. Kozen, Automata and Computability, Springer, New York (1997).
• 4 J.E. Hopcroft, J.D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, (1969).