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$
    – nir shahar
    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$
    – user145974
    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$
    – PDK
    Dec 5, 2021 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.