Content deleted Content added
Added details in introduction that completely defines push down automata for readers already familiar with Turing machine. |
Undid revision 1234278984 by Matthew V. Milone (talk): several is correct |
||
| (39 intermediate revisions by 30 users not shown) | |||
Line 1:
{{short description|Type of automaton}}
{{More citations needed|date=April 2022}}
{{Automata theory}}
In the [[theory of computation]], a branch of [[theoretical computer science]], a '''pushdown automaton''' ('''PDA''') is
a type of [[Automata theory|automaton]] that employs a [[Stack (data structure)|stack]].
Pushdown automata are used in theories about what can be computed by machines. They are more capable than [[finite-state machine]]s but less capable than [[Turing machine]]s (see [[#Turing machines|below]]).
[[Deterministic pushdown automata]] can recognize all [[deterministic context-free language]]s while nondeterministic ones can recognize all [[context-free language]]s, with the former often used in [[parser]] design.
A pushdown automaton is computationally equivalent to a 'restricted' Turing Machine (TM) with two tapes which is restricted in following manner- On the first tape, the TM can only read the input and move from left to right (it cannot make changes). On the second tape, it can only 'push' and 'pop' data. Or equivalently, it can read, write and move left and right with the restriction that the only action it can perform at each step is to either delete the left most character in the string (pop) or add an extra character left to the left most character in the string (push).▼
The term "pushdown" refers to the fact that the [[Stack (abstract data type)|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 access to and operations on deeper elements. Stack automata can recognize a strictly larger set of languages than pushdown automata.<ref name="Hopcroft.Ullman.1967"/>
Line 15 ⟶ 14:
[[Image:Pushdown-overview.svg|thumb|340px|A diagram of a pushdown automaton]]
A [[finite-state machine]] just looks at the input signal and the current state: it has no stack to work with, and therefore is unable to access previous values of the input. It
# It can use the top of the stack to decide which transition to take.
# It can manipulate the stack as part of performing a transition.
Line 46 ⟶ 45:
*<math>F \subseteq Q</math> is the set of ''accepting states''
An element <math>(p,a,A,q,\alpha) \in \delta</math> is a transition of <math>M</math>. It has the intended meaning that <math>M</math>, in state <math>p \in Q</math>, on the input <math>a \in \Sigma \cup \{\varepsilon\}</math> and with <math>A \in \Gamma</math> as topmost stack symbol, may read <math>a</math>, change the state to <math>q</math>, pop <math>A</math>, replacing it by pushing <math>\alpha \in \Gamma^*</math>. The <math>(\Sigma \cup \{\varepsilon\})</math> component of the transition relation is used to formalize that the PDA can either read a letter from the input, or proceed leaving the input untouched.{{
In many texts<ref name="Hopcroft.Ullman.1979"/>{{rp|110}}<!---more ref.s needed to substantiate 'many'---> the transition relation is replaced by an (equivalent) formalization, where
Line 108 ⟶ 107:
There seems to be no generally used representation for PDA. Here we have depicted the instruction <math>(p,a,A,q,\alpha)</math> by an edge from state {{mvar|p}} to state {{mvar|q}} labelled by <math>a; A/\alpha</math> (read {{mvar|a}}; replace {{mvar|A}} by <math>\alpha</math>).
=== Explanation ===
[[Image:Pda-steps.svg|thumb|214px|accepting computation for {{val|0011}}]]
The following illustrates how the above PDA computes on different input strings. The subscript {{mvar|M}} from the step symbol <math>\vdash</math> is here omitted.
Line 125 ⟶ 123:
}}
==
Every [[context-free grammar]] can be transformed into an equivalent nondeterministic pushdown automaton. The derivation process of the grammar is simulated in a leftmost way. Where the grammar rewrites a nonterminal, the PDA takes the topmost nonterminal from its stack and replaces it by the right-hand part of a grammatical rule (''expand''). Where the grammar generates a terminal symbol, the PDA reads a symbol from input when it is the topmost symbol on the stack (''match''). In a sense the stack of the PDA contains the unprocessed data of the grammar, corresponding to a pre-order traversal of a derivation tree.
Line 134 ⟶ 132:
# <math>(1,a,a,1,\varepsilon)</math> for each terminal symbol <math>a</math> (''match'')
The PDA accepts by empty stack. Its initial stack symbol is the grammar's start symbol.<ref>{{
For a context-free grammar in [[Greibach normal form]], defining (1,γ) ∈ δ(1,''a'',''A'') for each grammar rule ''A'' → ''a''γ also yields an equivalent nondeterministic pushdown automaton.<ref name="Hopcroft.Ullman.1979">{{cite book | isbn=0-201-02988-X | author=John E. Hopcroft and Jeffrey D. Ullman | title=Introduction to Automata Theory, Languages, and Computation | location=Reading/MA | publisher=Addison-Wesley | year=1979 | url-access=registration | url=https://archive.org/details/introductiontoau00hopc }}</ref>{{rp|115}}
Line 140 ⟶ 138:
The converse, finding a grammar for a given PDA, is not that easy. The trick is to code two states of the PDA into the nonterminals of the grammar.
'''Theorem.''' For each pushdown automaton <math>M</math> one may construct a context-free grammar <math>G</math> such that {{nobr|<math>N(M)=L(G)</math>.}}<ref name="Hopcroft.Ullman.1979"/>{{rp|116}}
The language of strings accepted by a deterministic pushdown automaton (DPDA) is called a [[deterministic context-free language]]. Not all context-free languages are deterministic.{{#tag:ref|The set of even-length [[Palindrome#Computation theory|palindromes]] of bits can't be recognized by a deterministic PDA, but is a [[context-free language]], with the [[context-free grammar|grammar]] ''S'' → ε <nowiki>|</nowiki> 0''S''0 <nowiki>|</nowiki> 1''S''1.<ref>{{cite book|author1=John E. Hopcroft |author2=Rajeev Motwani |author3=Jeffrey D. Ullman | title=Introduction to Automata Theory, Languages, and Computation| year=2003| publisher=Addison Wesley}} Here: Sect.6.4.3, p.249</ref>|group=note}} As a consequence, the DPDA is a strictly weaker variant of the PDA. Even for [[regular language]]s, there is a size explosion problem: for any [[General recursive function|recursive function]] <math>f</math> and for arbitrarily large integers <math>n</math>, there is a PDA of size <math>n</math> describing a regular language whose smallest DPDA has at least <math>f(n)</math> states.<ref>{{
A finite automaton with access to two stacks is a more powerful device, equivalent in power to a [[Turing machine]].<ref name="Hopcroft.Ullman.1979"/>{{rp|171}} A [[linear bounded automaton]] is a device which is more powerful than a pushdown automaton but less so than a Turing machine.{{#tag:ref|Linear bounded automata are acceptors for the class of context-sensitive languages,<ref name="Hopcroft.Ullman.1979"/>{{rp|225}} which is a proper superclass of the context-free languages, and a proper subclass of Turing-recognizable (i.e. [[recursively enumerable]]) languages.<ref name="Hopcroft.Ullman.1979"/>{{rp|228}}|group=note}}
==Turing machines==
▲A pushdown automaton is computationally equivalent to a 'restricted' Turing Machine (TM) with two tapes which is restricted in the following manner- On the first tape, the TM can only read the input and move from left to right (it cannot make changes). On the second tape, it can only 'push' and 'pop' data. Or equivalently, it can read, write and move left and right with the restriction that the only action it can perform at each step is to either delete the left
A GPDA is a PDA which writes an entire string of some known length to the stack or removes an entire string from the stack in one step.▼
That a PDA is weaker than a TM can be brought down to the fact that the procedure 'pop' deletes some data. In order to make a PDA as strong as a TM, we need to save somewhere the data lost through 'pop'. We can achieve this by introducing a second stack. In the TM model of PDA of last paragraph, this is equivalent to a TM with 3 tapes, where the first tape is the read-only input tape, and the 2nd and the 3rd tape are the 'push and pop' (stack) tapes. In order for such a PDA to simulate any given TM, we give the input of the PDA to the first tape, while keeping both the stacks empty. It then goes on to push all the input from the input tape to the first stack. When the entire input is transferred to the 1st stack, now we proceed like a normal TM, where moving right on the tape is the same as popping a symbol from the 1st stack and pushing a (possibly updated) symbol into the second stack, and moving left corresponds to popping a symbol from the 2nd stack and pushing a (possibly updated) symbol into the first stack. We hence have a PDA with 2 stacks that can simulate any TM.
==Generalization==
▲A generalized pushdown automaton (GPDA) is a PDA
A GPDA is formally defined as a 6-tuple:
Line 169 ⟶ 173:
:<math>\begin{array}{lcl}
\delta
\\
\delta
\\
&\vdots&
\\
\delta
\\
\delta
\\
\delta
\\
&\vdots&
\\
\delta
\end{array}</math>
==Stack
As a generalization of pushdown automata, Ginsburg, Greibach, and Harrison (1967) investigated '''stack automata''', which may additionally step left or right in the input string (surrounded by special endmarker symbols to prevent slipping out), and step up or down in the stack in read-only mode.<ref>{{cite journal| author=Seymour Ginsburg, Sheila A. Greibach and Michael A. Harrison| title=Stack Automata and Compiling| journal=J. ACM| year=1967| volume=14| number=1| pages=172–201| doi=10.1145/321371.321385| doi-access=free}}</ref><ref>{{cite journal| author=Seymour Ginsburg, Sheila A. Greibach and Michael A. Harrison| title=One-Way Stack Automata| journal=J. ACM| year=1967| volume=14| number=2| pages=389–418| doi=10.1145/321386.321403| doi-access=free}}</ref>
A stack automaton is called ''nonerasing'' if it never pops from the stack. The class of languages accepted by nondeterministic, nonerasing stack automata is ''[[NSPACE]]''(''n''<sup>2</sup>), which is a superset of the [[context-sensitive languages#Computational properties|context-sensitive languages]].<ref name="Hopcroft.Ullman.1967">{{cite journal|author1=John E. Hopcroft |author2=Jeffrey D. Ullman | title=Nonerasing Stack Automata| journal=Journal of Computer and System Sciences| year=1967| volume=1| number=2| pages=166–186| doi=10.1016/s0022-0000(67)80013-8| doi-access=free}}</ref> The class of languages accepted by deterministic, nonerasing stack automata is ''[[DSPACE]]''(''n''⋅log(''n'')).<ref name="Hopcroft.Ullman.1967"/>
==Alternating pushdown automata {{anchor|Alternating}}==
Line 197 ⟶ 201:
States in <math>Q_\exists</math> and <math>Q_\forall</math> are called ''existential'' resp. ''universal''. In an existential state an APDA nondeterministically chooses the next state and accepts if ''at least one'' of the resulting computations accepts. In a universal state APDA moves to all next states and accepts if ''all'' the resulting computations accept.
The model was introduced by [[Ashok K. Chandra|Chandra]], [[Dexter Kozen|Kozen]] and [[Larry Stockmeyer|Stockmeyer]].<ref name="ChandraKozen1981">{{cite journal|last1=Chandra|first1=Ashok K.|last2=Kozen|first2=Dexter C.|last3=Stockmeyer|first3=Larry J.|title=Alternation|journal=Journal of the ACM|volume=28|issue=1|year=1981|pages=114–133|issn=0004-5411|doi=10.1145/322234.322243|doi-access=free}}</ref> [[Richard E. Ladner|Ladner]], [[Richard J. Lipton|Lipton]] and [[Larry Stockmeyer|Stockmeyer]]<ref name="LadnerLipton1984">{{cite journal|last1=Ladner|first1=Richard E.|last2=Lipton|first2=Richard J.|last3=Stockmeyer|first3=Larry J.|title=Alternating Pushdown and Stack Automata|journal=SIAM Journal on Computing|volume=13|issue=1|year=1984|pages=135–155|issn=0097-5397|doi=10.1137/0213010}}</ref> proved that this model is equivalent to [[EXPTIME]] i.e. a language is accepted by some APDA [[if, and only if]], it can be decided by an exponential-time algorithm.
Aizikowitz and Kaminski<ref name="AizikowitzKaminski2011">{{cite book|last1=Aizikowitz|first1=Tamar|title=Computer Science – Theory and Applications|last2=Kaminski|first2=Michael|chapter=LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata|volume=6651|year=2011|pages=345–358|issn=0302-9743|doi=10.1007/978-3-642-20712-9_27|series=Lecture Notes in Computer Science|isbn=978-3-642-20711-2}}</ref> introduced ''synchronized alternating pushdown automata'' (SAPDA) that are equivalent to [[conjunctive grammar]]s in the same way as nondeterministic PDA are equivalent to context-free grammars.
==See also==
* [[Stack machine]]▼
* [[Context-free grammar]]
* [[Finite automaton]]▼
* [[Counter automaton]]
* [[Queue automaton]]
▲* [[Stack machine]]
==Notes==
Line 214 ⟶ 218:
<references/>
* {{cite book | author = Michael Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 0-534-94728-X | author-link = Michael Sipser | url-access = registration | url = https://archive.org/details/introductiontoth00sips }} Section 2.2: Pushdown Automata, pp. 101–114.
* Jean-Michel Autebert, Jean Berstel, Luc Boasson, [http://www-igm.univ-mlv.fr/~berstel/Articles/1997CFLPDA.pdf Context-Free Languages and Push-Down Automata], in: G. Rozenberg, A. Salomaa (eds.), Handbook of Formal Languages, Vol. 1, Springer-Verlag, 1997,
==External links==
* [
* [https://www.elstel.org/coan CoAn], another simulator for several machine types including nondeterministic pushdown automata (C++, Windows, Linux, MacOS)
| |||