Transition Function of 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 Transition function

Design a PDA for accepting a language {0ⁿ1ⁿ | 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 in PDA

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)  

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, 00Z₀)  

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 “0Z₀”

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 “Z₀”

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, ∈, Z₀) = (q1, ∈)   // Z₀ represents epsilon

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