of several configuration sequences; if one of them leads to an accepting configuration after reading the complete input string, the latter is said to belong to the language accepted by the automaton. Formal definition We use standard formal language notation: denotes the set of finite-length strings over alphabet and denotes the empty string. A PDA is formally defined as a 7-tuple: where is a finite set of states is a finite set which is called the input alphabet is a finite set which is called the stack alphabet is a finite subset of , the transition relation is the start state is the initial stack symbol is the set of accepting states An element is a transition of . It has the intended meaning that , in state , on the input and with as topmost stack symbol, may read , change the state to , pop , replacing it by pushing . The component of the transition relation is used to formalize that the PDA can either read a letter from the input, or proceed leaving the input untouched. In many texts the transition relation is replaced by an (equivalent) formalization, where is the transition function, mapping into finite subsets of Here contains all possible actions in state with on the stack, while reading on the input. One writes for example precisely when because . Note that finite in this definition is essential. Computations In order to formalize the semantics of the pushdown automaton a description of the current situation is introduced. Any 3-tuple is called an instantaneous description (ID) of , which includes the current state, the part of the input tape that has not been read, and the contents of the stack (topmost symbol written first). The transition relation defines the step-relation of on instantaneous descriptions. For instruction there exists a step , for every and every . In general pushdown automata are nondeterministic meaning that in a given instantaneous description there may be several possible steps. Any of these steps can be chosen in a computation. With the above definition in each step always a single symbol (top of the stack) is popped, replacing it with as many symbols as necessary. As a consequence no step is defined when the stack is empty. Computations of the pushdown automaton are sequences of steps. The computation starts in the initial state with the initial stack symbol on the