What are Pushdown Automata?
The PDA have an input tape, a finite control, and a stack. The stack is a string of symbols from some alphabet. The leftmost symbol of the stack is considered to be at the “top” of the stack. The device will be nondeterministic, having some finite number of choices of moves in each move. There are two types of moves. In the first one an input symbol is used. Depending on the input symbol, the top symbol on the stack, and the state of a finite control, a number of choices are possible. Each choice consists of a next state for the finite control and a (possibly empty) string of symbols to replace the top of the stack symbol. After selecting a choice, the input head is advanced by one symbol.
The second type of move is similar to the first, except that the input symbol is not used, and the input head is not advanced after the move. This type of move allows the PDA to manipulate the stack without regarding input symbols.
A pushdown accepter in configuration (q,j ,s):
The program P is a finite sequence of instructions, each taking one of the forms:
In each case, the state q is the label of the instruction, and the state q' is the successor state. Each state in Q labels at most one type of instruction, read, write, or scan. If q is any state, j any string in S* , and s any string in U* , then (q,j ,s) is a configuration of M. The string s usually called the stack, and the symbol under the stack head the top stack symbol.