Pushdown automaton is a type of automaton that employs a stack. Pushdown automata are used in theories about what can be computed by machines. They are more capable than finite-state machines but less capable than Turing machines.

A Pushdown Automata (PDA) can be defined as :

Q is the set of states

∑ is the set of input symbols

Γ is the set of pushdown symbols (which can be pushed and popped from stack)

q0 is the initial state

Z is the initial pushdown symbol (which is initially present in stack)

F is the set of final states

δ is a transition function which maps Q x { ∑ ∪ ɛ } x Γ into Q x Γ *. In a given state, PDA will read input symbol and stack symbol (top of the stack) and move to a new state and change the symbol of stack.