title: npda for the language number a's less than or equal to 3 times the number of b's
body: <p>I am trying to construct an npda for L = {w ∈ {a,b}*| n<strong>a</strong>(w) &lt;= 3*n<strong>b</strong>(w)}. 
  This means that for every <strong>b</strong> there can be at most 3 <strong>a</strong>'s. </p>
  
  <p>First of all, this is what I have done so far. 
  From the start state, we push a single "<strong>a</strong>" on to the stack. (at the end of the day, we need to see this "<strong>a</strong>" to get to the final state, if there were more than 3 a's for every b, we would have popped this "<strong>a</strong>", and we would not reach the final state).</p>
  
  <p>Then for every <strong>b</strong> on the string, I would push 3 <strong>a</strong>'s. For every <strong>a</strong> on the input I would pop a single "<strong>a</strong>".</p>
  
  <p>At the end, if there is an <strong>a</strong> on the stack we go to the final state.</p>
  
  <p><a href="https://i.stack.imgur.com/Bno9X.jpg" rel="nofollow noreferrer">Click here for the npda drawing</a></p>
  
  <p>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)</p>
  
  <p>If we were to run the npda for baaa. This would work fine. </p>
  
  <p>Reading nothing (lambda) we push <strong>a</strong>. Then we read <strong>b</strong>, and push <strong>aaa</strong>. 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. </p>
  
  <p>The issue is that this construction only works when <strong>b</strong> supplies 3 a's to the stack in excess first before the <strong>a</strong>'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 <strong>a</strong> we would have to pop an <strong>a</strong>. Reading the second a, no operation that can be done. There is nothing on the stack and we cant push an <strong>a</strong> because that would mess everything up. </p>
  
  <p>How could I fix this construction or is there a better npda construction for the language. </p>
  
  <p>I have been working on this for days. Help would be greatly appreciated. </p>
  
  <p>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. </p>
  
  <p>Thanks </p>