Xrthnty

In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) 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.^[1]
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 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. It chooses a new state, the result of following the transition. A pushdown automaton (PDA) 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 (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.

Formal definition

We use standard formal language notation: Γ∗displaystyle Gamma ^* denotes the set of strings over alphabet Γdisplaystyle Gamma and εdisplaystyle varepsilon denotes the empty string.

A PDA is formally defined as a 7-tuple:

M=(Q,Σ,Γ,δ,q0,Z,F)displaystyle M=(Q,Sigma ,Gamma ,delta ,q_0,Z,F)
where

• 
  Qdisplaystyle Q is a finite set of states
  


• 
  Σdisplaystyle Sigma is a finite set which is called the input alphabet
  


• 
  Γdisplaystyle Gamma is a finite set which is called the stack alphabet
  


• 
  δdisplaystyle delta is a finite subset of Q×(Σ∪ε)×Γ×Q×Γ∗displaystyle Qtimes (Sigma cup varepsilon )times Gamma times Qtimes Gamma ^*, the transition relation
  


• 
  q0∈Qdisplaystyle q_0in Q is the start state
  


• 
  Z∈Γdisplaystyle Zin Gamma is the initial stack symbol
  


• 
  F⊆Qdisplaystyle Fsubseteq Q is the set of accepting states
  

An element (p,a,A,q,α)∈δdisplaystyle (p,a,A,q,alpha )in delta is a transition of Mdisplaystyle M. It has the intended meaning that Mdisplaystyle M, in state p∈Qdisplaystyle pin Q, on the input a∈Σ∪εdisplaystyle ain Sigma cup varepsilon and with A∈Γdisplaystyle Ain Gamma as topmost stack symbol, may read adisplaystyle a, change the state to qdisplaystyle q, pop Adisplaystyle A, replacing it by pushing α∈Γ∗displaystyle alpha in Gamma ^*. The (Σ∪ε)displaystyle (Sigma cup varepsilon ) 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 (equivalent) formalization, where

• 
  δdisplaystyle delta is the transition function, mapping Q×(Σ∪ε)×Γdisplaystyle Qtimes (Sigma cup varepsilon )times Gamma into finite subsets of Q×Γ∗displaystyle Qtimes Gamma ^*
  

Here δ(p,a,A)displaystyle delta (p,a,A) contains all possible actions in state pdisplaystyle p with Adisplaystyle A on the stack, while reading adisplaystyle a on the input. One writes for example δ(p,a,A)=(q,BA)displaystyle delta (p,a,A)=(q,BA) precisely when (q,BA)∈(q,BA),(q,BA)∈δ(p,a,A),displaystyle (q,BA)in (q,BA),(q,BA)in delta (p,a,A), because ((p,a,A),(q,BA))∈δdisplaystyle ((p,a,A),(q,BA))in delta . Note that finite in this definition is essential.

Computations

a step of the pushdown automaton

In order to formalize the semantics of the pushdown automaton a description of the current situation is introduced. Any 3-tuple (p,w,β)∈Q×Σ∗×Γ∗displaystyle (p,w,beta )in Qtimes Sigma ^*times Gamma ^* is called an instantaneous description (ID) of Mdisplaystyle M, 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). The transition relation δdisplaystyle delta defines the step-relation ⊢Mdisplaystyle vdash _M of Mdisplaystyle M on instantaneous descriptions. For instruction (p,a,A,q,α)∈δdisplaystyle (p,a,A,q,alpha )in delta there exists a step (p,ax,Aγ)⊢M(q,x,αγ)displaystyle (p,ax,Agamma )vdash _M(q,x,alpha gamma ), for every x∈Σ∗displaystyle xin Sigma ^* and every γ∈Γ∗displaystyle gamma in Gamma ^*.

In general pushdown automata are nondeterministic meaning that in a given instantaneous description (p,w,β)displaystyle (p,w,beta ) there may be several possible steps. Any of these steps can be chosen in a computation.
With the above definition in each step always a single symbol (top of the stack) is popped, replacing it 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 q0displaystyle q_0 with the initial stack symbol Zdisplaystyle Z on the stack, and a string wdisplaystyle w on the input tape, thus with initial description (q0,w,Z)displaystyle (q_0,w,Z).
There are two modes of accepting. The pushdown automaton either accepts by final state, which means after reading its input the automaton reaches an accepting state (in Fdisplaystyle F), or it accepts by empty stack (εdisplaystyle varepsilon ), which means after reading its input the automaton empties its stack. The first acceptance mode uses the internal memory (state), the second the external memory (stack).

Formally one defines

1. 
   L(M)=w∈Σ∗"> (final state)


2. 
   N(M)=(q0,w,Z)⊢M∗(q,ε,ε)displaystyle N(M)=win Sigma ^* with q∈Qdisplaystyle qin Q (empty stack)

Here ⊢M∗displaystyle vdash _M^* represents the reflexive and transitive closure of the step relation ⊢Mdisplaystyle vdash _M meaning any number of consecutive steps (zero, one or more).

For each single pushdown automaton these two languages need to 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 Mdisplaystyle M one may construct a pushdown automaton M′displaystyle M' such that L(M)=N(M′)displaystyle L(M)=N(M'), and vice versa, for each pushdown automaton Mdisplaystyle M one may construct a pushdown automaton M′displaystyle M' such that N(M)=L(M′)displaystyle N(M)=L(M')

Example

The following is the formal description of the PDA which recognizes the language 0n1n∣n≥0displaystyle 0^n1^nmid ngeq 0 by final state:

PDA for 0n1n∣n≥0displaystyle 0^n1^nmid ngeq 0
(by final state)

M=(Q, Σ, Γ, δ, q0, Z, F)displaystyle M=(Q, Sigma , Gamma , delta , q_0, Z, F), where

• 
  states: Q=p,q,rdisplaystyle Q=p,q,r
  


• 
  input alphabet: Σ=0,1displaystyle Sigma =0,1
  


• 
  stack alphabet: Γ=A,Zdisplaystyle Gamma =A,Z
  


• 
  start state: q0=pdisplaystyle q_0=p
  


• 
  start stack symbol: Z
  


• 
  accepting states: F=rdisplaystyle F=r
  

The transition relation δdisplaystyle delta consists of the following six instructions:

(p,0,Z,p,AZ)displaystyle (p,0,Z,p,AZ),

(p,0,A,p,AA)displaystyle (p,0,A,p,AA),

(p,ϵ,Z,q,Z)displaystyle (p,epsilon ,Z,q,Z),

(p,ϵ,A,q,A)displaystyle (p,epsilon ,A,q,A),

(q,1,A,q,ϵ)displaystyle (q,1,A,q,epsilon ), and

(q,ϵ,Z,r,Z)displaystyle (q,epsilon ,Z,r,Z).

In words, the first two instructions say that in state p any time the symbol 5000000000000000000♠0 is read, one A is pushed onto the stack. Pushing symbol A on top of another A is formalized as replacing top A by AA (and similarly for pushing symbol A on top of a Z).

The third and fourth instructions say that, at any moment the automaton may move from state p to state q.

The fifth instruction says that in state q, for each symbol 7000100000000000000♠1 read, one A is popped.

Finally, the sixth instruction says that the machine may move from state q to accepting state r only when the stack consists of a single Z.

There seems to be no generally used representation for PDA. Here we have depicted the instruction (p,a,A,q,α)displaystyle (p,a,A,q,alpha ) by an edge from state p to state q labelled by a;A/αdisplaystyle a;A/alpha (read a; replace A by αdisplaystyle alpha ).

Understanding the computation process

accepting computation for 7001110000000000000♠0011

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

PDA and 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 (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.

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

1. 
   (1,ε,A,1,α)displaystyle (1,varepsilon ,A,1,alpha ) for each rule A→αdisplaystyle Ato alpha (expand)


2. 
   (1,a,a,1,ε)displaystyle (1,a,a,1,varepsilon ) for each terminal symbol adisplaystyle a (match)

The PDA accepts by empty stack. Its initial stack symbol is the grammar's start symbol.^{[citation needed]}

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.^[2]:115

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 Mdisplaystyle M one may construct a context-free grammar Gdisplaystyle G such that N(M)=L(G)displaystyle N(M)=L(G).^[2]:116

The language of strings accepted by a deterministic pushdown automaton is called a deterministic context-free language. Not all context-free languages are deterministic.^{[note 1]} As a consequence, the DPDA is a strictly weaker variant of the PDA and there exists no algorithm for converting a PDA to an equivalent DPDA, if such a DPDA exists.^{[citation needed]}

A finite automaton with access to two stacks is a more powerful device, equivalent in power to a Turing machine.^[2]:171 A linear bounded automaton is a device which is more powerful than a pushdown automaton but less so than a Turing machine.^{[note 2]}

Generalized pushdown automaton (GPDA)

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.

A GPDA is formally defined as a 6-tuple:

M=(Q, Σ, Γ, δ, q0, F)displaystyle M=(Q, Sigma , Gamma , delta , q_0, F)

where Q,Σ,Γ,q0displaystyle Q,Sigma ,,Gamma ,,q_0, and Fdisplaystyle F are defined the same way as a PDA.

δdisplaystyle ,delta : Q×Σϵ×Γ∗⟶P(Q×Γ∗)displaystyle Qtimes Sigma _epsilon times Gamma ^*longrightarrow P(Qtimes Gamma ^*)

is the transition function.

Computation rules for a GPDA are the same as a PDA except that the ai+1displaystyle a_i+1's and bi+1displaystyle b_i+1's are now strings instead of symbols.

GPDA's and PDA's are equivalent in that if a language is recognized by a PDA, it is also recognized by a GPDA and vice versa.

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

Let δ(q1,w,x1x2⋅xm)⟶(q2,y1y2...yn)displaystyle delta (q_1,w,x_1x_2cdot x_m)longrightarrow (q_2,y_1y_2...y_n) be a transition of the GPDA

where q1,q2∈Q,w∈Σϵ,x1,x2,…,xm∈Γ∗,m≥0,y1,y2,…,yn∈Γ∗,n≥0displaystyle q_1,q_2in Q,win Sigma _epsilon ,x_1,x_2,ldots ,x_min Gamma ^*,mgeq 0,y_1,y_2,ldots ,y_nin Gamma ^*,ngeq 0.

Construct the following transitions for the PDA:

δ′(q1,w,x1)⟶(p1,ϵ)δ′(p1,ϵ,x2)⟶(p2,ϵ)⋮δ′(pm−1,ϵ,xm)⟶(pm,ϵ)δ′(pm,ϵ,ϵ)⟶(pm+1,yn)δ′(pm+1,ϵ,ϵ)⟶(pm+2,yn−1)⋮δ′(pm+n−1,ϵ,ϵ)⟶(q2,y1)displaystyle beginarraylcldelta ^'(q_1,w,x_1)&longrightarrow &(p_1,epsilon )\delta ^'(p_1,epsilon ,x_2)&longrightarrow &(p_2,epsilon )\&vdots &\delta ^'(p_m-1,epsilon ,x_m)&longrightarrow &(p_m,epsilon )\delta ^'(p_m,epsilon ,epsilon )&longrightarrow &(p_m+1,y_n)\delta ^'(p_m+1,epsilon ,epsilon )&longrightarrow &(p_m+2,y_n-1)\&vdots &\delta ^'(p_m+n-1,epsilon ,epsilon )&longrightarrow &(q_2,y_1)endarray

Stack automaton

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.^[4][5]
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²), which is a superset of the context-sensitive languages.^[1] The class of languages accepted by deterministic, nonerasing stack automata is DSPACE(n⋅log(n)).^[1]

Alternating pushdown automata

An alternating pushdown automaton (APDA) is a pushdown automaton with a state set

• 
  Q=Q∃∪Q∀displaystyle Q=Q_exists cup Q_forall where Q∃∩Q∀=∅displaystyle Q_exists cap Q_forall =emptyset .

States in Q∃displaystyle Q_exists and Q∀displaystyle Q_forall 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 Chandra, Kozen and Stockmeyer.^[6]Ladner, Lipton and Stockmeyer^[7] proved that this model is equivalent to EXPTIME i.e. a language is accepted by some APDA iff it can be decided by an exponential-time algorithm.

Aizikowitz and Kaminski^[8] 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.

See also

• Stack machine


• Context-free grammar


• Finite automaton


• Counter automaton


• Queue automaton

Notes

References

• 
  Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 2.2: Pushdown Automata, pp. 101–114.


• Jean-Michel Autebert, Jean Berstel, Luc Boasson, Context-Free Languages and Push-Down Automata, in: G. Rozenberg, A. Salomaa (eds.), Handbook of Formal Languages, Vol. 1, Springer-Verlag, 1997, 111-174.

External links

• 
  JFLAP, simulator for several types of automata including nondeterministic pushdown automata


• 
  CoAn, another simulator for several machine types including nondeterministic pushdown automata (C++, Windows, Linux, MacOS)