Introduction To PushDown Automata

In order to accept Context free language we need a machine which is similer to finit automata. It is nothing but a finit automata to which a memory is added i.e stack.

                   FA + Stack=PDA

(Q,∑,δ,q0,Z0,F,X)

Q : Finite Set of states

∑ : Input symbol

δ  : Transition Function

q0 : Initial Symbol

Z: Bottom of the stack

F  :  Set of final states

X  : Stack alphabet( means what are the symbol that we allow to be present on to the top of the statck)

 PDA is of two type:

1. Deteministic PDA:

 

δ  : Q x {∑ ∪ ∈} x X     ---->   Q x X*

 

 

2. Non Detesministic PDA:

 

δ  : Q x {∑ ∪ ∈} x X      ---->    2Q x X*

 

 

0Comment