# How to design PDA for this language?

I'm having a hard time trying to build the PDA for this language: $$L=\{a^nb^m: n,m \geq 1 \land m=4n+2\}$$

I don't know how many $$a's$$ should I push into the stack when reading $$a$$, and how many $$a's$$ should I pop out of the stack when reading $$b$$, and how to reach the final state. Can anyone help me with this? Thanks for your help!

• Hint: push 4 pop 1 Dec 4, 2021 at 22:16

The language can be rewritten as $$a^nb^{4n}bb$$ which is to say that for every a's there are 4 b's and after that, we just add two b's. One strategy would be to push four stack symbols after you read 1 a. And then pop those stack symbols one by one on reading b's. After your stack is empty (i.e. resets to the starting symbol) then you just proceed to read two b's. One small caveat, do remember that your language must contain at least 1 a since $$n \ge 1$$
• How can I read the remaining $2$ $b's$ when there is no $a's$ ? How should I draw the states ?
• You can read any input symbol irrespective of what's on the stack by making use of the $\varepsilon$ symbol.