deterministic pushdown automaton

{{Redirect|DPDA|the Australian political party|Drew Pavlou Democratic Alliance}}

In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton. The class of deterministic pushdown automata accepts the deterministic context-free languages, a proper subset of context-free languages.{{cite book | author = Michael Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 0-534-94728-X | page = [https://archive.org/details/introductiontoth00sips/page/102 102] | author-link = Michael Sipser | url-access = registration | url = https://archive.org/details/introductiontoth00sips/page/102 }}

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.

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, or final, 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 $*$ is the Kleene star, meaning that $\Gamma^{*}$ is "the set of all finite strings (including the empty string $\varepsilon$ ) of elements of $\Gamma$ ", $\varepsilon$ 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 those languages that are accepted by final state and are prefix-free: no word in the language is the prefix of another word in the language.{{cite book |last=Soltys-kulinicz |first=Michael |date=2018 |title=An Introduction To The Analysis Of Algorithms |edition=3rd |url=https://books.google.com/books?id=VEBPDwAAQBAJ&pg=PA193 |publisher=World Scientific |isbn=9789813235922 |pages=193,195}}{{cite book |first1=John E. |last1=Hopcroft |first2=Rajeev |last2=Motwani |first3=Jeffrey D. |last3=Ullman |title=Introduction to Automata Theory, Languages, and Computation |edition=3rd |title-link=Introduction to Automata Theory, Languages, and Computation |publisher=Addison-Wesley |year=2006 |isbn=0-321-45536-3 |pages=234,254}}

The usual acceptance criterion is final state, and it is this acceptance criterion which is used to define the deterministic context-free languages.

Languages recognized

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

Not all context-free languages are deterministic. This makes the DPDA a strictly weaker device than the PDA. For example, the language L_p of even-length palindromes on the alphabet of 0 and 1 has the context-free grammar S → 0S0 | 1S1 | ε. If a DPDA for this language exists, and it sees a string 0ⁿ, it must use its stack to memorize the length n, in order to be able to distinguish its possible continuations {{nowrap|0ⁿ 11 0ⁿ ∈ L_p}} and {{nowrap|0ⁿ 11 0ⁿ⁺² ∉ L_p.}} Hence, after reading {{nowrap|0ⁿ 11 0ⁿ,}} comparing the post-"11" length to the pre-"11" length will make the stack empty again. For this reason, the strings {{nowrap|0ⁿ 11 0ⁿ 0ⁿ 11 0ⁿ ∈ L_p}} and {{nowrap|0ⁿ 11 0ⁿ 0ⁿ⁺² 11 0ⁿ⁺² ∉ L_p}} cannot be distinguished.{{cite book | last = Hopcroft | author-link = John Hopcroft | first = John |author2=Rajeev Motwani | author3-link = Jeffrey Ullman |author3=Jeffrey Ullman | title = Introduction to Automata Theory, Languages, and Computation |edition=2 | year = 2001 | publisher = Addison-Wesley | pages = [https://archive.org/details/introductiontoau00john_537/page/n264 249]–253 | author2-link = Rajeev Motwani | title-link = Introduction to Automata Theory, Languages, and Computation }}

Restricting the DPDA to a single state reduces the class of languages accepted to the LL(1) languages,{{Cite journal | last1 = Kurki-Suonio | first1 = R. | title = Notes on top-down languages | doi = 10.1007/BF01946814 | journal = BIT | volume = 9 | issue = 3 | pages = 225–238 | year = 1969 | s2cid = 60912010 }} which is a proper subclass of the DCFL.{{cite journal| last1=Rosenkrantz| first1=D. J.| last2=Stearns| first2=R. E.| title=Properties of Deterministic Top Down Grammars| journal=Information and Control| year=1970| volume=17| issue=3| pages=226–256| doi=10.1016/s0019-9958(70)90446-8| doi-access=free}} Here: p.246–247 In the case of a PDA, this restriction has no effect on the class of languages accepted.

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 because one has to avoid infinite computations and correctly handle transitions that manipulate the stack without reading input symbols.{{Citation |last1=Hopcroft |first1=John E. |title=Deterministic pushdown automata |date=1969-01-01 |work=Formal languages and their relation to automata |url=https://dl.acm.org/doi/10.5555/1096945.C1065808 |access-date=2024-05-29 |place=USA |publisher=Addison-Wesley Longman Publishing Co., Inc. |last2=Ullman |first2=Jeffrey D.}}

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 =

Géraud Sénizergues (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,{{cite book|last=Sénizergues|first=Géraud|author-link=Géraud Sénizergues|contribution=The equivalence problem for deterministic pushdown automata is decidable|title=Proc. Int. Coll. on Automata, Languages, and Programming (ICALP)|year=1997|volume=1256|pages=671–681|doi=10.1007/3-540-63165-8_221|series=Lecture Notes in Computer Science|isbn=978-3-540-63165-1}} — Full version: {{cite report | url=http://dept-info.labri.u-bordeaux.fr/~ges/lalb_l.ps | author=Géraud Sénizergues | title=L(A) = L(B)? | institution=Universite Bordeaux, LaBRI | type=Technical Report 1161-97 | year=1997 }}{{cite journal | author=Géraud Sénizergues | title=Fundamental study: L(A) = L(B)? decidability results from complete formal systems | journal=Theoretical Computer Science | volume=251 | number=1–2 | pages=1–166 | year=2001 | doi=10.1016/S0304-3975(00)00285-1 | doi-access= }}

{{cite journal | author=Géraud Sénizergues | title=L(A) = L(B)? A simplified decidability proof | journal=Theoretical Computer Science | volume=281 | number=1–2 | pages=555–608 | year=2002 | doi=10.1016/S0304-3975(02)00027-0 | doi-access=free }} a proof that earned him the 2002 Gödel Prize. For nondeterministic PDA, equivalence is undecidable.