npda for the language number a's less than or equal to 3 times the number of b's

Question

I am trying to construct an npda for L = {w ∈ {a,b}*| na(w) <= 3*nb(w)}. This means that for every b there can be at most 3 a's.

First of all, this is what I have done so far. From the start state, we push a single "a" on to the stack. (at the end of the day, we need to see this "a" to get to the final state, if there were more than 3 a's for every b, we would have popped this "a", and we would not reach the final state).

Then for every b on the string, I would push 3 a's. For every a on the input I would pop a single "a".

At the end, if there is an a on the stack we go to the final state.

Click here for the npda drawing

So lets consider a string where nb(w)= 1 and na(w) = 3. We could have string of the sort baaa, aaab, abaa, aaba. (there are others too)

If we were to run the npda for baaa. This would work fine.

Reading nothing (lambda) we push a. Then we read b, and push aaa. The stack content is (aaaa). Then we read a and pop a single a. We do this 3 times and stack becomes (a). After reading the string, there is there is an a left on the stack so we are good to go to final state.

The issue is that this construction only works when b supplies 3 a's to the stack in excess first before the a's show up on the string. If we run the npda on the string aaab, this would no longer work. We would have single a on the stack, reading the first a we would have to pop an a. Reading the second a, no operation that can be done. There is nothing on the stack and we cant push an a because that would mess everything up.

How could I fix this construction or is there a better npda construction for the language.

I have been working on this for days. Help would be greatly appreciated.

Also know that I am very new to npda so it could be that I am doing something that is fundamentally wrong. So, be clear in the explanation.

Thanks

Answer 1

Not sure I can give you my exact answer because I'm pretty sure we're in the same 335 class. lol.

The main issue is that you're not accounting for all possibilities.

The initial state has 14 possibilities in its loop and it can branch into 2 branches that return to the initial state. It also has a transition to the final state upon seeing end of stack symbol.

All of these except the ones noted is done on the initial state's loop.

Upon seeing a:

a input:
    Push a onto the stack

b input:
    You can pop it or replace it with 1 or 2 b's
    Or
    You can pop one b
    Or
    You can pop 2 or 3 b's (Done by branching into 2 different branches of
    states that do just that, respectively, and return to the initial state)

Upon seeing b:

a input:
    Pop b (Only way to meet criteria for final state)

b input:
    Push 0 to 3 b's

Upon seeing end of stack symbol:

empty string input:
    Go to final state.

I can possibly help more if I had another means of communication.