I have to design a PDA that recognizes the language $\{a^nb^m \mid 0<n\leq m\leq3n\}$

I tried to partition the stack into 3 partitions with the first partition being the size of $n$ with character A, the second partition being the size of $2n$ with character B, and the third partition size of $n$ with character A.

I got stuck with this idea. Can anyone help me with this?


1 Answer 1


Roughly speaking, the PDA consists of two phases.

During the first phase, the PDA reads $a$s. For each $a$ that it reads, it nondeterministically pushes either $A$, or $AA$, or $AAA$ to the stack.

During the second phase, the PDA reads $b$s, popping one $A$ per $b$ read. At the end, the stack needs to be empty.

Details left to you.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.