Pushdown Automata Operation : Push and Pop with example

In Pushdown automata the stack head always scans the top symbol of the stack. It performs two basic operations.

• Push Operations: Push operations add a new symbol from the stack symbol ‘Γ’ at the top of the stack.
• Pop Operations: Pop operations remove the top symbol from the stack.

A PDA has finitely many numbers of states which form a set Q. For each move, the state is changed according to the evaluation of a transition function ‘δ’.

δ: (Q x (Σ ∪{ε}) x Γ) → (Q x Γ*)

Some basic operation descriptions on PDA:

Here is the description of the operational behavior of the pushdown automata.

δ(q, a, v) ∈ (p, uv) means that if the tape head reads symbol a, the stack head reads symbol v, and the PDA is in state q, then one of the possible moves is that the next state is p, v is replaced by uv (i.e. stack top element ∪ stack previous string) at stack, and the tape head moves one cell to the right.

2.

δ(q, ε, v) ∈ (p, u) means this is a ε-transition. Here finite control stack read ‘ε’ (null symbol) and move to the next state and update the stack position as well.

3.

δ(q, a, z₀) ∈ (p, uz₀) means that first push operation is performed on the stack when the finite state control scan the first element form the input string.

4.

δ(q, a, z₀) ∈ (p, uu) means that self loop push operation is performed on the stack when the finite state control scan the same element form the input string.

5.

δ(q, a, v) ∈ (p, ε) means that pop operation is performed on the stack.

6.

δ(q, ε, z₀) ∈ (q, ε) means that pop operation is performed on the stack.

Note:

There are some special states: an initial state q₀ and a set F of accepting states usually called final state. Initially, the PDA is in the initial state q₀ and the head scans the leftmost cell. The tape holds an input string. The stack is empty with the initial stack symbol z₀. When the tape head gets off the tape, the PDA stops. An input string x is accepted by the PDA if the PDA stops at an accepting state (and the stack is empty). Otherwise, the input string is rejected by the PDA.