Pushdown automaton

The term "pushdown" refers to the fact that the 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.

A pushdown automaton can also manipulate the stack, as part of performing a transition.

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.

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.

[citation needed] In many texts[2] the transition relation is replaced by an (equivalent) formalization, where Here

Computations In order to formalize the semantics of the pushdown automaton a description of the current situation is introduced.

, which includes the current state, the part of the input tape that has not been read, and the contents of the stack (topmost symbol written first).

In general pushdown automata are nondeterministic meaning that in a given instantaneous description

represents the reflexive and transitive closure of the step relation

For each single pushdown automaton these two languages need to have no relation: they may be equal but usually this is not the case.

Taken over all pushdown automata both acceptance conditions define the same family of languages.

The following illustrates how the above PDA computes on different input strings.

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.

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.

Technically, given a context-free grammar, the PDA has a single state, 1, and its transition relation is constructed as follows.

[3] 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.

The trick is to code two states of the PDA into the nonterminals of the grammar.

Even for regular languages, there is a size explosion problem: for any recursive function

[b] For many non-regular PDAs, any equivalent DPDA would require an unbounded number of states.

[c] 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).

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'.

A generalized pushdown automaton (GPDA) is a PDA that writes an entire string of some known length to the stack or removes an entire string from the stack in one step.

One can formulate an analytic proof for the equivalence of GPDA's and PDA's using the following simulation: Let

Construct the following transitions for the PDA: 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.

[1] The class of languages accepted by deterministic, nonerasing stack automata is DSPACE(n⋅log(n)).

[13] Ladner, Lipton and Stockmeyer[14] 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[15] introduced synchronized alternating pushdown automata (SAPDA) that are equivalent to conjunctive grammars in the same way as nondeterministic PDA are equivalent to context-free grammars.