# Push Down Automata

**Configuration**

It contains finite control , input tape and a stack and Finite control contains finite number of states.

Read head or read pointer is used to read the input symbol from the input tape.

The symbols can be pushed or popped from stack , which is used to keep track of previous symbols.

For every string finite control starts from the initial state.If the string valid finite control reaches to the final state at end of input.

**Acceptance Mechanisms**

Acceptance by final state (universal mechanism)

Acceptance by empty stack (local mechanism)

Acceptance by empty stack and final state.

**CFL =~ PDA by empty stack =~ PDA by final state =~ PDA by empty stack and final state =~ CFG.**

**Operations**

The operations on push down automata are as follows:

**PUSH :**Some finite sequence of symbols is pushed into the stack.

**POP :**One symbol at the top of the stack is popped.

**BIPASS :**i.e do nothing stack contents unchanged while state may be changed

**REPLACE :**Replace one symbol at the top of the stack.

**Specification**

PDA = ( Q , ⅀ , êž† , áºŸ ,q0 , Z0 , F ) is a 7 tuple notation

Where,

Q is a set of finite states.

⅀ is the input alphabet which contains finite number of input symbols.

êž† is the stack alphabet which contains a finite number of stack symbols.

áºŸ is a transition function.

(i) ( DPDA ) áºŸ : Q ⤫ ( ⅀ ⋃ { ∈ } ) ⤫ êž† → Q ⤫ êž†

(ii) ( NPDA ) áºŸ : Q ⤫ ( ⅀ ⋃ { ∈ } ) ⤫ êž† → 2

^{Q⤬}

^{ êž† }(only finite sub – sets ).

q0 is a single start state q0 ∈ Q.

Z0 is the start symbol Z0 ∈ êž†.

F is the set of final states F ⊆ Q. If acceptance is by empty stack method then F is not specified.

## No comments