Pushdown automaton


In the theory of computation, a branch of theoretical computer science, a pushdown automaton is
a type of automaton that employs a stack.
Pushdown automata are used in theories about what can be computed by machines. They are more capable than finite-state machines but less capable than Turing machines.
Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic ones can recognize all context-free languages, with the former often used in parser design.
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. Stack automata can recognize a strictly larger set of languages than pushdown automata.
A nested stack automaton allows full access, and also allows stacked values to be entire sub-stacks rather than just single finite symbols.

Informal description

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 differs from a finite state machine in two ways:
  1. It can use the top of the stack to decide which transition to take.
  2. 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. 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.
Put together: Given an input symbol, current state, and stack symbol, the automaton can follow a transition to another state, and optionally manipulate the stack.
If, in every situation, at most one such transition action is possible, then the automaton is called a deterministic pushdown automaton . 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.

Formal definition

We use standard formal language notation: denotes the set of finite-length strings over alphabet and denotes the empty string.
A PDA is formally defined as a 7-tuple:
where
  • is a finite set of states
  • is a finite set which is called the input alphabet
  • is a finite set which is called the stack alphabet
  • is a finite subset of, the transition relation
  • is the start state
  • is the initial stack symbol
  • is the set of accepting states
An element is a transition of. It has the intended meaning that, in state, on the input and with as topmost stack symbol, may read, change the state to, pop, replacing it by pushing. The 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 the transition relation is replaced by an formalization, where
  • is the transition function, mapping into finite subsets of
Here contains all possible actions in state with on the stack, while reading on the input. One writes for example precisely when because. Note that finite in this definition is essential.

Computations

In order to formalize the semantics of the pushdown automaton, a description of the current situation is introduced. Any 3-tuple is called an instantaneous description of, which includes the current state, the part of the input tape that has not been read, and the contents of the stack. The transition relation defines the step-relation of on instantaneous descriptions. For instruction there exists a step, for every and every.
In general, pushdown automata are nondeterministic, meaning that in a given instantaneous description there may be several possible steps. Any of these steps can be chosen in a computation.
With the above definition, in each step a single symbol is always popped, and replaced with as many symbols as necessary. As a consequence, no step is defined when the stack is empty.
Computations of the pushdown automaton are sequences of steps. The computation starts in the initial state with the initial stack symbol on the stack, and a string on the input tape—thus, with initial description.
There are two modes of accepting. The pushdown automaton either accepts by final state, which means that after reading its input the automaton reaches an accepting state, or else it accepts by empty stack, which means that after reading its input the automaton empties its stack. The first acceptance mode uses the internal memory, the second the external memory.
Formally one defines
  1. with and
  2. with
Here represents the reflexive and transitive closure of the step relation, meaning any number of consecutive steps.
For each single pushdown automaton, these two languages need have no relation; they may be equal, but usually this is not the case. A specification of the automaton should also include the intended mode of acceptance. Taken over all pushdown automata, both acceptance conditions define the same family of languages.
Theorem. For each pushdown automaton one may construct a pushdown automaton such that, and vice versa, for each pushdown automaton one may construct a pushdown automaton such that

Example

The following is the formal description of the PDA which recognizes the language by final state:
Image:Pda-example.svg|thumb|200px|PDA for

, where
  • states:
  • input alphabet:
  • stack alphabet:
  • start state:
  • start stack symbol:
  • accepting states:
The transition relation consists of the following six instructions:
In words, the first two instructions say that in state any time the symbol is read, one is pushed onto the stack. Pushing symbol on top of another is formalized as replacing top by .
The third and fourth instructions say that, at any moment the automaton may move from state to state.
The fifth instruction says that in state, for each symbol read, one is popped.
Finally, the sixth instruction says that the machine may move from state to accepting state only when the stack consists of a single.
There seems to be no generally used representation for PDA. Here we have depicted the instruction by an edge from state to state labelled by .

Explanation

The following illustrates how the above PDA computes on different input strings. The subscript from the step symbol is here omitted.

Context-free languages

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. Where the grammar generates a terminal symbol, the PDA reads a symbol from input when it is the topmost symbol on the stack. 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.
  1. for each rule
  2. for each terminal symbol
The PDA accepts by empty stack. Its initial stack symbol is the grammar's start symbol.
For a context-free grammar in Greibach normal form, defining ∈ δ for each grammar rule A → aγ also yields an equivalent nondeterministic pushdown automaton.
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 one may construct a context-free grammar such that
The language of strings accepted by a deterministic pushdown automaton is called a deterministic context-free language. Not all context-free languages are deterministic. As a consequence, the DPDA is a strictly weaker variant of the PDA. Even for regular languages, there is a size explosion problem: for any recursive function and for arbitrarily large integers, there is a PDA of size describing a regular language whose smallest DPDA has at least states. For many non-regular PDAs, any equivalent DPDA would require an unbounded number of states.
A finite automaton with access to two stacks is a more powerful device, equivalent in power to a Turing machine. A linear bounded automaton is a device which is more powerful than a pushdown automaton but less so than a Turing machine.

Turing machines

A pushdown automaton is computationally equivalent to a "restricted" Turing Machine 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. On the second tape, it can only "push" and "pop" data; i.e., the TM can read, write, and move left and right on the second tape, with the restriction that the only action it can perform at each step is to either delete the left-most character in the string or add an extra character left to the left-most character in the string.
That a PDA is weaker than a TM can be boiled down to the fact that the "pop" procedure deletes some data. In order to make a PDA as strong as a TM, we need to save this lost data somewhere; this can be achieved by introducing a second stack. In the aforementioned TM model of pushdown automata, this is equivalent to a TM with three tapes, wherein the first tape is the read-only input tape, and both the second and third tapes are "push" and "pop" 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 onto the first stack. When the entire input is transferred to the first stack, operation proceeds as in a normal TM: moving right on the tape is the same as popping a symbol from the first stack and pushing a symbol onto the second stack, and moving left corresponds to popping a symbol from the second stack and pushing a symbol onto the first stack—hence, we now have a two-stack PDA that can simulate any TM.