We will now consider a new notion of automata pushdown automata (PDA). PDAs are finite automatons with a stack, i.e. a data structure which can be used to store an arbitrary number of symbols (hence PDAs have an infinite set of states) but which can be only accessed in a last-in-first-out (LIFO) fashion. The languages which can be recognized by PDA are precisely the context free languages.