# 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 -

##### {a^{n}b^{n}|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,ε)

Greibach Normal Form

Deterministic PDA