Definition: A pushdown automaton (PDA) is
a 7-tuple M = (Q, S, G, R, s, S, F),
where
• Q is a finite set of states
• S is an input
alphabet
• G is a pushdown
alphabet
• R is a finite set of rules of the form:
Apa
® wq
where A Î G, p, q Î Q, a Î S È {e}, w Î G*
• s Î Q is the start state
• S Î G is the start pushdown symbol
• F Í Q is a set of final
states