Transition Rules and Transition Diagrams - Non Deterministic Push Down Automata

 

Transition Rules in a NPDA

An NPDA (Nondeterministic Pushdown Automaton) extends an NFA with a stack.

So, a transition in NPDA depends on:

1. Current state (q ∈ Q)

2. Current input symbol (a ∈ Σ ∪ {ε}) – we may consume input or take an ε-move.

3. Top of the stack symbol (X ∈ Γ, where Γ is the stack alphabet).

Based on these, the automaton nondeterministically chooses one or more possible actions.

---

Formal Definition of Transition Function

For NPDA, the transition function is defined as:

$$\delta : Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \;\;\to\;\; \mathcal{P}(Q \times \Gamma^*)$$

This means:

• Input: (current state, current input symbol or ε, top of stack symbol)

• Output: a set of choices, where each choice is:

  • A new state (q′)

  • A replacement for the top stack symbol (a string γ ∈ Γ*).

---

Interpretation

• Pop: If we replace the top with ε, it means we remove the top symbol.

• Push: If we replace the top with multiple symbols, they are pushed onto the stack (rightmost ends up on top).

• Change: If we replace the top with another symbol, it’s like rewriting the top.

• No change: If we replace it with the same symbol, stack remains unchanged.

---

Example Transition Rule

Consider the language L = {aⁿbⁿ : n ≥ 0}.L = {ab, aabb, aaabbb, aaaabbbb, ......}

• NPDA idea: push each a onto stack, then pop one a for each b.

• Transitions:

1. δ(q₀, a, Z₀) = { (q₀, aZ₀) }

   • On reading a, with bottom marker Z₀, push a.

2. δ(q₀, a, a) = { (q₀, aa) }

   • On reading a, with a on stack, push another a.

3. δ(q₀, b, a) = { (q₁, ε) }

   • On reading b, pop a.

4. δ(q₁, b, a) = { (q₁, ε) }

   • Continue popping A’s for each b.

5. δ(q₁, ε, Z₀) = { (q_accept, Z₀) }

   • If input finished and only bottom marker remains, accept.

---

Key Difference (NPDA vs DPDA)

• NPDA: δ may give multiple possible next moves (nondeterministic choices).

• DPDA: δ must give at most one move for each configuration.

---

✅ So in short:

Transition rules in NPDA tell us how the automaton changes its state and stack contents, based on the current input symbol (or ε) and the stack’s top symbol.

Transition Diagram

 A transition diagram (state diagram) for a Pushdown Automaton is very useful .We  can visually connect the rules with machine operation. Let’s do this with the classic example L = { aⁿbⁿ : n ≥ 0 }

As we want to design a NPDA, thus every time 'a' comes before 'b'. When ‘a’ comes then push it in stack and if again ‘a’ comes then also push it.

After that, when ‘b’ comes then pop one 'a' from the stack each time. So, at the end if the stack becomes empty then we can say that the string is accepted by the PDA.