computation-theory

NPDA for L= {w ∈ {a,b}*: number of a's is twice the number of b's}

I have been trying to find a NPDA for this language but I can't come up with anything that will accept all of the words in the language. I did try making its accepting condition an empty stack and using the stack alphabet {$ a b} but maybe I should try something else?

Solution

  • Maybe you are looking the equivalent Grammar for the given Regular Expression.
    If so maybe this one with the following productions:

    S->AAb | SAAb | ASAb | AASb | AAbS
A->a

    Some Tests:

    aab : S->AAb->aAb->aab
aaaabb : S-> AASb -> AA(AAb)b -> aaaabb

    Could check also with other example and see if fit on all cases.

    If fine always should have on
    Result = (2*count_of_b) for a, count_b

    Looking twice, A->a can be removed and have only:

    S->aab|Saab|aSab|aaSb|aabS

    Test:

    aaaabb : aaSb(S_4)->aaaabb(S_1), etc.