0
Construct a PDA accepting the following language :

$L = {a^nb^ma^n / m,n>=1}$

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: May 2014

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

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

where

1. Q – Finite set of states
2. є- Input symbol
3. δ- Transition function
4. $q_0$ - Initial state
5. $z_0$ – Bottom of the stack
6. F- Set of final states
7. Γ- 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, ε)$

0