Question: Construct a PDA accepting the following language :
0

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

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: May 2014

ADD COMMENTlink
modified 3.3 years ago  • written 3.3 years ago by gravatar for Pooja Joshi Pooja Joshi740
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, ε)$

enter image description here

ADD COMMENTlink
written 3.3 years ago by gravatar for Pooja Joshi Pooja Joshi740
Please log in to add an answer.