Pushdown automaton

Out-of-context languages, described by out-context grammars, are recognized (accepted) by pushdown automata. Informally, a pushdown automaton is a finite state automaton to which has been added a stack of unlimited capacity initially empty. The execution of a pushdown automaton on a given word is similar to that of a finite state automaton. However, at each step, the pushdown automaton consults the top of its stack and eventually replaces it with a series of symbols.

A pushdown automaton is a quintuplet A = (T, P, Q, M, S0) such that:

  • T is the terminal vocabulary,
  • P is the stack vocabulary (containing in particular an initial empty stack symbol, noted ⊥),
  • Q is a finite set of states,
  • M is a set of transitions,
  • S0 ∈ Q is the initial state.

The stack vocabulary contains all the symbols that can appear on the stack, and is not necessarily distinct from the terminal vocabulary (we can have T ∩ P ≠ ∅).

A transition in the pushdown automaton is similar to that of a finite state automaton, except that it also specifies the manipulation of the stack. A transition of M is of the form
(state, symbol, top_stack) → (new_state, action_stack) such as:

  • state and new state are states of Q,
  • symbol is either a terminal symbol of T, or ∅, meaning that the automaton does not look at the word,
  • top_stack is either a symbol of P, or ∅, meaning that the automaton does not look at the top of the stack,
  • action_stack is either:
    • « Unstack the symbol at the top of the stack », or
    • « Unstack the symbol at the top of the stack and then stack a sequence of symbols » or
    • « Stack a series of symbols », or
    • « Do nothing ».

The operation of the automaton A = (T, P, Q, M, S0) is defined as follows:

A configuration of the automaton is characterized by a triplet: (S, m, p) with S ∈ Q, m ∈ T and p ∈ P that is to say, a current state S, a sequence m of terminal symbols (corresponding to the end of the word to be analyzed) and a sequence p of stack symbols (corresponding to the current state of the stack).

The configuration (S0, m0, p0) is derivable in one step of the configuration (S, m, p)
(denoted (S, m, p) ⇒ (S0, m0, p0)) if: (S, u, v) → (S0, action_stack) is a transition of M, m = u.m0 (the word m to be analyzed begins with the symbol u), the symbol at the top of the stack p is v. p0 is the stack obtained after performing the action_stack p.

A word w is accepted by the pushdown automaton A if (S0, w, ⊥) ⇒ (S, ε, ⊥) where ⊥ is the empty stack symbol. The language L(A) accepted by A is the set of words accepted by A.

In other words, a word is accepted by the automaton if there is a sequence of transitions from the initial state and empty stack, leading to the entire reading of the word and the stack again empty. Note that some pushdown automata can accept on final states without empty stack. Moreover, any recognizing automaton by final state has an equivalent automaton recognizing by empty stack.

The pushdown automata that we have defined accept a word when there is a derivation leading to a configuration where the stack is empty and the word fully read. For this reason, they are pushdown automata with empty stack. Another definition of the pushdown automaton is that of the automaton accepting only with a final state. Such an automaton also specifies a set F ⊆ Q of final states. A word is accepted if there is a derivation leading to a configuration where the state is final (the stack is not necessarily empty).

A stack automaton is said to be deterministic if any given situation or configuration corresponds to only one transition.

There are out-of-context languages that are not supported by any deterministic pushdown automaton. The languages accepted by deterministic pushdown automata thus form a subclass of out-of-context languages: the class of deterministic out-of-context languages.

Example

Here is an example of a non-deterministic pushdown automaton. Let the pushdown automaton recognizes the language of the words formed on {a, b} and containing the same number of a and b: A = (T, P, Q, M, q) such that: T = {a, b}, P = {a, b}, Q = {q} and the following transition matrix M :

State Symbol Top_stack New_state Action_stack
q a q push(a)
q b q push(b)
q a a q push(a)
q b b q push(b)
q a b q pop(b)
q b a q pop(a)

The derivation of this automaton on the word w = aabbabba is:

state word stack
q aabbabba
q abbabba a⊥
q bbabba aa⊥
q babba a⊥
q abba
q bba a⊥
q ba
q a b⊥
q ε

As for the finite state automata, we can draw pushdown automatons with a graph. The arcs have the following information: read symbol, depilated symbol; stacked symbol.
For example the arc a, A; ε will read the symbol a, unstack a symbol A at the top of the stack. Note that ε or λ represents « do nothing ».