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.
Pushdown automata states description diagram
Pushdown automata states description diagram

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.

  1. Pushdown automata basic operation 1
    Pushdown automata basic operation

δ(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.

Pushdown automata basic operation 2
Pushdown automata basic operation

δ(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.

Pushdown automata basic operation 3
Pushdown automata basic operation

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

4.

Pushdown automata basic operation 4
Pushdown automata basic operation

δ(q, a, z0) ∈ (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.

Pushdown automata basic operation 5
Pushdown automata basic operation

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

6.

Pushdown automata basic operation 6
Pushdown automata basic operation

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

Note:

There are some special states: an initial state q0 and a set F of accepting states usually called final state. Initially, the PDA is in the initial state q0 and the head scans the leftmost cell. The tape holds an input string. The stack is empty with the initial stack symbol z0. 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.

LEAVE A REPLY

Please enter your comment!
Please enter your name here