Pushdown Automata is a finite automata with extra memory called stack which helps Pushdown automata to recognize Context Free Languages.

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.

Example : Define the pushdown automata for language {anbn | n > 0}

Solution : M = where Q = { q0, q1 } and ∑ = { a, b } and Γ = { A, Z } and δ is given by

δ( q0, a, Z ) = { ( q0, AZ ) }

δ( q0, a, A) = { ( q0, AA ) }

δ( q0, b, A) = { ( q1, ɛ) }

δ( q1, b, A) = { ( q1, ɛ) }

δ( q1, ɛ, Z) = { ( q1, ɛ) }

Let us see how this automata works for aaabbb.