0
$\begingroup$

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!

Improve this question
$\endgroup$
1
  • $\begingroup$ Hint: push 4 pop 1 $\endgroup$ Commented Dec 4, 2021 at 22:16

1 Answer 1

Reset to default
3
$\begingroup$

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$

Improve this answer
$\endgroup$
2
  • $\begingroup$ How can I read the remaining $2$ $b's$ when there is no $a's$ ? How should I draw the states ? $\endgroup$ Commented Dec 5, 2021 at 3:17
  • $\begingroup$ You can read any input symbol irrespective of what's on the stack by making use of the $\varepsilon$ symbol. $\endgroup$ Commented Dec 5, 2021 at 16:52