stack, and a string on the input tape, thus with initial description . There are two modes of accepting. The pushdown automaton either accepts by final state, which means after reading its input the automaton reaches an accepting state (in ), or it accepts by empty stack (), which means after reading its input the automaton empties its stack. The first acceptance mode uses the internal memory (state), the second the external memory (stack). Formally one defines with and (final state) with (empty stack) Here represents the reflexive and transitive closure of the step relation meaning any number of consecutive steps (zero, one or more). For each single pushdown automaton these two languages need to have no relation: they may be equal but usually this is not the case. A specification of the automaton should also include the intended mode of acceptance. Taken over all pushdown automata both acceptance conditions define the same family of languages. Theorem. For each pushdown automaton one may construct a pushdown automaton such that , and vice versa, for each pushdown automaton one may construct a pushdown automaton such that Example The following is the formal description of the PDA which recognizes the language by final state: , where states: input alphabet: stack alphabet: start state: start stack symbol: accepting states: The transition relation consists of the following six instructions: , , , , , and . In words, the first two instructions say that in state any time the symbol is read, one is pushed onto the stack. Pushing symbol on top of another is formalized as replacing top by (and similarly for pushing symbol on top of a ). The third and fourth instructions say that, at any moment the automaton may move from state to state . The fifth instruction says that in state , for each symbol read, one is popped. Finally, the sixth instruction says that the machine may move from state to accepting state only when the stack consists of a single . There seems to be no generally used representation for PDA. Here we have depicted the instruction by an edge from state to state labelled by (read ; replace by ). Understanding the computation process The following illustrates how the above PDA computes on different input strings. The subscript from the step symbol is here omitted. PDA and context-free languages Every context-free grammar can be transformed into