Editing Pushdown automaton (section)

== Informal description ==

[[Image:Pushdown-overview.svg|thumb|340px|A diagram of a pushdown automaton]]
A [[finite-state machine]] only considers 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 can only choose a new state, the result of following the transition. A '''pushdown automaton (PDA)''' differs from a finite state machine in two ways:
# 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.

A pushdown automaton reads a given input string from left to right. In each step, it chooses a transition by indexing a table by input symbol, current state, and the symbol at the top of the stack. <!---wrong, or at least strongly misleading, for properly nondeterministic PDA:---This means that those three parameters completely determine the transition path that is chosen.---><!---don't know what this sentence is supposed to mean:---Pushdown automata add the stack as a parameter for choice.---> A pushdown automaton can also manipulate the stack, as part of performing a transition. The manipulation can be to push a particular symbol to the top of the stack, or to pop off the top of the stack. The automaton can alternatively ignore the stack, and leave it as it is. <!---misleading for properly nondeterministic PDA:---The choice of manipulation (or no manipulation) is determined by the transition table.--->

Put together: Given an input symbol, current state, and stack symbol, the automaton can follow a transition to another state, and optionally manipulate (push or pop) the stack.

If, in every situation, at most one such transition action is possible, then the automaton is called a '''[[deterministic pushdown automaton]] (DPDA)'''. In general, if several actions are possible, then the automaton is called a '''general''', or '''nondeterministic''', '''PDA'''. A given input string may drive a nondeterministic pushdown automaton to one of several configuration sequences; if one of them leads to an accepting configuration after reading the complete input string, the latter is said to belong to the ''language accepted by the automaton''.
<!---has been said more precisely above:---Nondeterministic PDAs are able to handle situations where more than one choice of action is available.---><!---don't know what these paragraphs are supposed to mean; automata don't create 'instances' during their operation; PDAs are a theoretical model, implemetation problems aren't an issue here, see [[Earley parser]], [[LR parser]], etc., instead---:In principle, it is enough{{clarify|date=December 2016}} to create in every such case new automaton instances that will handle the extra choices.

=== Backtracking ===

The problem with multiple automata per choice is that in practice most of these instances fail. This can severely affect the automaton's performance as the execution of multiple instances is a costly operation. Situations such as these can be identified in the design phase of the automaton by examining{{how|date=December 2016}} the grammar the automaton uses. This makes possible the use of [[backtracking]] in every such case in order to improve the performance of pushdown automaton.--->