deterministic pushdown automaton

A pushdown automaton $M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },T,q_0,\perp ,F)$ is usually called “non-deterministic” because the image of the transition function $T$ is a subset of $Q\times {\mathrm{\Gamma }}^{*}$, which may possibly contain more than one element. In other words, the transition from one configuration to the next is not uniquely determined. When there is uniqueness, $M$ is called “deterministic”.

Formally, a deterministic pushdown automaton, or DPDA for short, is a non-deterministic pushdown automaton $M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },T,q_0,\perp ,F)$ where the transition function $T$ has the following properties: for any $p\in Q$, $a\in \mathrm{\Sigma }$, and $A\in \mathrm{\Gamma }$,

1. $T(p,a,A)\cup T(p,\lambda ,A)$ is at most a singleton,

2. $T(p,a,A)\cap T(p,\lambda ,A)=\mathrm{\varnothing }$.

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)\ne T(p,\lambda ,A)$, so that when a $\lambda$-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.

Nevertheless, any regular language can be accepted by a DPDA on empty stack, and any language accepted by a DPDA on final state is unambiguous, and, as a result, $ℱ$ is a proper subset of the family of all context-free languages. This is quite unlike the case for finite automata: every non-deterministic finite automaton is equivalent to a deterministic finite automaton. A language in $ℱ$ called a deterministic language.

Some examples: the set of palindromes $\{u\in {\mathrm{\Sigma }}^{*}\mid u=\mathrm{rev}(u)\}$ is unambiguous, but not deterministic. The language $\{a^m{b}^n\mid m\ge n\ge 0\}$ is deterministic, but not prefix-free, and hence can not be accepted by any DPDA on empty stack. The language $\{a^n{b}^n\mid n\ge 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 $LR(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 $ℰ\ne ℱ$ 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:

  $$T(p,a,A)\cup T(p,\lambda ,A)=\mathrm{\varnothing },$$

  or the stack is emptied before the last input symbol is read: a configuration $(p,u,\lambda )$ is reached and $u$ is not empty.

• $M$ consumes the last input symbol, and continues processing because of $\lambda$-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.

Title	deterministic pushdown automaton
Canonical name	DeterministicPushdownAutomaton
Date of creation	2013-03-22 18:56:00
Last modified on	2013-03-22 18:56:00
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	14
Author	CWoo (3771)
Entry type	Definition
Classification	msc 03D10
Classification	msc 68Q42
Classification	msc 68Q05
Synonym	DPDA
Related topic	ContextFreeLanguage
Related topic	AmbiguousGrammar
Defines	deterministic
Defines	deterministic language
Defines	deterministic context-free