Pushdown Automata

The Pushdown Automata is investigated by Sheila Greibach. It is a part in theoretical computer science which employs a stack. It is called "pushed-down" as it works on the principal of stack i.e., Last In First Out. Always the operation is first performed on the top most element. The push down automata is less capable than a Turning Machine and more capable than a Finite State Machine.

Pushdown automata machine recognizes best for a wider class of language. The context free language is language recognized by pushdown automata. This also plays an important role in determining the organization of computer programs being processed by a compiler.



Components of Pushdown Automata

These are the following components of Pushdown automata -

  • Input tape: The input tape is divided in many cells. The input head is read-only and may only move from left to right, each cell in turn.
  • Finite control: The finite control has some pointer which focuses the current symbol which is to be read.
  • Stack: In stack, elements are inserted and removed from only one end. In PDA, the stack is utilized to store the items temporarily.


Formal Definition of Push Down Automata

The formal definition of a Pushdown Automata is defined as -

(Q,Σ,Γ,δ,q0,Z0,F)

Q- It is the finite set of states,
Σ - finite set of input alphabet,
Γ - finite set of stack alphabet,
δ - transition function, Q x (Σ ∪ ∈) x Γ x Q x Γ*
q0 - start state,
Z0 - initial pushdown symbol,
F - the set of finite state.


Turnstile Notation

These are the some symbols used for connecting pairs of ID's.

!--- represents one move and is called turnstile notation.
!---* represents a sequence of moves.




Instantaneous Description (ID) of PDA

The Instantaneous description is called as an informal notation, and clarifies how a Push down automata (PDA) computes a given input string and makes a decision whether that string is accepted or rejected. The instantaneous description of Pushdown Automata is represented by -

(q,w,s)

q - current state,
w - unconsumed part or remaining input,
s - stack contents, top at the left.


Example of Pushdown Automata

Here is the example of Pushdown Automata -

{anbn|n >= 0}
Q = {s,p,q}, Σ = {a,b}, Γ = {A}, F = {q}

where δ contains the following transitions -

(s,a,ε) -> (s,A) (s,b,ε) -> (s,B) (s,ε,ε) -> (p,ε) (p,a,A) -> (p,ε) (p,b,B) -> (p,ε) (p,ε,Z) -> (q,ε)