Transition Function in PDA

There are three essential cases in Pushdown Automata (PDA) to understand the functionality of the transition function.  

As we know, the transition function is Q × (∑ ∪ {ε}) x Γ à Q × Γ *. Where

  • Γ represents the symbol which is at the Top of the Stack before the transition function
  • Γ* represents all the symbols that are present in the Stack after the Transition function.

Example of PDA

Design a PDA for accepting a language {0n1n | n>=1}.

According to the given language, consider an Input string with an equal number of 0s and 1s as “0011∈”. Whenever the epsilon (∈) occurs as input, then that transition is the last.

So, we will apply a very simple logic is that for every single ‘1’ only one ‘0’ should get POP out from the stack.

Explanation of Transition Function

Let’s understand all three cases of transition function with a given input string.

Case 01: If the symbols of Γ and Γ* are different then PUSH the symbol of Γ in stack.

To perform the PUSH Operation for the first input “0”, the transition function and detail diagram are given below

δ(q0, 0, Z0) = (q0, 0Z0)  

Case 01 Pushdown Automata (PDA) Transition Function Step 01

Note: Z0 is the stack default value, which is also known as epsilon.

To perform the PUSH Operation for the second input “0”, the transition function and detail diagram are given below.

δ (q0, 0, 0) = (q0, 00Z0)  

Case 1 Pushdown Automata (PDA) Transition Function Step 02

Note: After each transition, the state can either change or remain the same.

Case 02: If the value of Γ is non-empty but the value of Γ* is epsilon (empty) then POP the value of Γ from stack. Let see the following transition function example

To perform the POP Operation for the third input “1”, the transition function and detail diagram are given below.

δ(q0, 1, 0) = (q0, ∈)  // Now stack hold value “0Z0

Case 2 Pushdown Automata (PDA) Transition Function Step 01

To perform the POP Operation for the fourth input “1”, the transition function and detail diagram are given below

δ(q0, 1, 0) = (q0, ∈)  // Now stack hold value “Z0

Case 2 Pushdown Automata (PDA) Transition Function Step 02

Note: It means both values are POP out from the stack through the above transition functions.

Case 03: If the value of Γ and Γ* are both the same (i.e. both empty) in value then there will be no change in stack. Let see the following transition function example

At this stage, the stack is empty (Z0), and the last Input string having the last symbol is epsilon (∈). So, there will be no change in the stack. The transition function with a detailed diagram is given below.

 δ (q0, ∈, Z0) = (q1, ∈)   // Z0 represents epsilon

Case 3 Pushdown Automata (PDA) Transition Function

The above transition function has no effect on the stack but can change the current state (i.e., q0 to q1).

In Pushdown Automata (PDA),

  • Only One Input symbol is read at a time.
  •  Only one input symbol is either PUSH or POP in the stack at a time.