Question: Construct a PDA accepting the following language :

0

0

A PDA is defined as a 7-tuple representation such as

(Q, є, δ, $q_0$, $z_0$,F,Γ)

where

- Q – Finite set of states
- є- Input symbol
- δ- Transition function
- $q_0$ - Initial state
- $z_0$ – Bottom of the stack
- F- Set of final states
- Γ- Stack alphabet

Here, we have $a^n$ same on both sides of $b^m$. So to solve this PDA, we will have to use ‘b’ characters as a delimiter rather than performing any action.

When we encounter the first $a^n$ , we shall push the ‘a’ characters and when we face the ‘b’ character, we move to the pop state.

For an input aabaa, the PDA is represented as

$δ(S,a,z_0) = (S,az_0)$

$δ(S,a,a) = (S,aa)$

$δ(S,b,a) = (A)$

$δ(A,a,a) = (A, ε)$

$δ(A, ε,z_0) = (C, ε)$

Please log in to add an answer.