Question

Construct a PDA that accepts the language L = { w ∈ { a , b } ∗ : n a ( w ) = n b ( w ) }, where n a ( w ) represents the number of a's that appear in the string w.

Answer 1

PDA that accepts L(languages) = { w ∈ { a , b } ∗ : n a ( w ) = n b ( w ) }

Let 'a' or 'b' push in STACK. it means if 'a' comes first let it push in stack.
if after 'a' again 'a' comes then let push it .

If 'b' comes first, push it in STACK ('a' did not yet come)
If 'b' again comes then push b in STACK.

Now if 'a' is at the top of STACK and 'b' comes then, pop 'a'
Similarily if 'b' is at top of STACK and 'a' comes then, pop 'b'

So in the end of the strings if the STACK is empty then we can say that CFL is accepted in the PDA.

Now,We designed PDA for the problem:

STACK Transiton Function

                δ(q0, a, Z) = (q0, aZ)     
                δ(q0, a, a) = (q0, aa)     
                δ(q0, b, Z) = (q0, bZ)     
                δ(q0, b, b) = (q0, bb)     
                δ(q0, b, a) = (q0, ε)     
                δ(q0, a, b) = (q0, ε)     

                δ(q0, ε, Z) = (qf, Z)

STACK Transiton Function

       δ(q0, a, Z) = (q0, aZ)   
       δ(q0, a, a) = (q0, aa)   
       δ(q0, b, Z) = (q0, bZ)   
       δ(q0, b, b) = (q0, bb)   
       δ(q0, b, a) = (q0, ε)   
       δ(q0, a, b) = (q0, ε)   

       δ(q0, ε, Z) = (qf, Z)
We will take one input string: "aabbbbaa"

Scan string from left to right
Now at First input is 'a' and we follow the rule:
input 'a' and stack alphabet Z, push the input 'a' into the STACK as : (a,Z/aZ) and state is q0
Second input is 'a' and so we follow the rule:
input 'a' and STACK alphabet 'a', push the input 'a' into the STACK as : (a,a/aa) and state will not change remain q0
Second input is 'b' and so we follow the rule:
Third input is 'b' and so we follow rule
on input 'b' and STACK alphabet 'a', pop the STACK with one '"a" as : (b,a/&epsiloon;) and state will not change remain qo
Fourth input is 'b'
taking input 'b' and STACK alphabet 'a', pop the STACK with one "a" as : (b,a/&epsiloon;) and state will remain qo
Fifth input is 'b'
on input 'b' and STACK alphabet Z, push the input "b"into the STACK as : (b,Z/bZ) and state will remain q0
Sixth input is 'b'
on input "b" and STACK alphabet 'a', push the input "b" into the STACK as : (b,b/bb) and state will remain q0
Seventh input is 'a'
on input 'a' and STACK alphabet 'b', pop the STACK with one 'b' as : (a,b/&epsiloon;) and state will remain q0
Eighth input is 'a'
on input 'a' and STACK alphabet 'b', pop the STACK with one 'b' as : (a,b/&epsiloon;) and state will remain q0
We reached end of the string, so we follow the rule:
on input ε and STACK alphabet Z, go to final state(qf) as -> (ε, Z/Z)