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

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

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


    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, ε)$

enter image description here

Please log in to add an answer.

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.


Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More