This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate? Excessive Violence Sexual Content Political / Social
Email Address:
Article Id: WHEBN0003972656 Reproduction Date:
In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton . The DPDA accepts the deterministic context-free languages, a proper subset of context-free languages.^{[1]}
Machine transitions are based on the current state and input symbol, and also the current topmost symbol of the stack. Symbols lower in the stack are not visible and have no immediate effect. Machine actions include pushing, popping, or replacing the stack top. A deterministic pushdown automaton has at most one legal transition for the same combination of input symbol, state, and top stack symbol. This is where it differs from the nondeterministic pushdown automaton.
A (not necessarily deterministic) PDA M can be defined as a 7-tuple:
where
M is deterministic if it satisfies both the following conditions:
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.
If L(A) is a language accepted by a PDA A it can also be accepted by a DPDA if and only if there is a single computation from the initial configuration until an accepting one for all strings belonging to L(A). If L(A) can be accepted by a PDA it is a context free language and if it can be accepted by a DPDA it is a deterministic context-free language.
Not all context-free languages are deterministic. This makes the DPDA a strictly weaker device than the PDA. For example, the language of even-length palindromes on the alphabet of 0 and 1 has the context-free grammar S → 0S0 | 1S1 | ε. An arbitrary string of this language cannot be parsed without reading all its letters first which means that a pushdown automaton has to try alternative state transitions to accommodate for the different possible lengths of a semi-parsed string.^{[2]}
Restricting the DPDA to a single state reduces the class of languages accepted to the LL(1) languages.^{[3]} In the case of a PDA, this restriction has no effect on the class of languages accepted.
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).
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,^{[4]} a proof that earned him the 2002 Gödel Prize. For nondeterministic PDA, equivalence is undecidable.
Computer science, Mathematics, Artificial intelligence, Theory of computation, Numerical analysis
Computer science, Automata theory, Formal language, String (computer science), Nondeterministic finite automaton
Computer science, Turing machine, Automata theory, Deterministic context-free language, Context-free language
Deterministic pushdown automaton, Nested word, Proper subset, Context-free language, Unambiguous grammar
Parsing, Formal language, Context-free grammar, Programming languages, Context-sensitive language
Formal grammar, Context-free grammars, Nested word, Proper subset, Deterministic context-free language