Mumbai University > Computer Engineering > Sem 4 > Theoretical Computer Science

Marks: 10M

Year: Dec 2016

Push down Automata

1. The pushdown automata will have input tape, finite control and stack.

2. The input tape is divided in many cells. At each cell only one input symbol is placed thus certain input string is placed on tape.

3. The finite control has some pointer which point the current symbol which is to be read.

4. At the end of input $ symbol is placed which indicates end of input.

1. The stack is such a structure in which you can push and remove the items from one end only. For example if you place some coins one above the other, then a stack of coin is fromed.
2. While removing a coin we can only remove the coin which is at the top.
3. Similarly while adding more coins to the stack we can placea new coin only on the topmost coin. Thus the stack of coin shows the clear cut use of only one end of the stack.
4. In the pushdown automata, we are using the stack for storing the items temporarily.
5. Inserting the symbol onto the stackis called push operation and removing a symbol from stack is called pop operation.