Pushdown Automata: Definition
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
21/50