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 -