construct a pushdown automata for L={a^mb^n where n<=m<=2n}?

Question

I was looking to understand the construction of pushdown automata for L={a^nb^m where n<=m<=2n}? I found this question on stack over itself.

here is what the answer said which I understood:

Here's the strategy: we can easily make a PDA that accepts a^n b^n, and we can easily make one that accepts a^n b^2n. Our language is a superset of these languages that also accepts anything with a number of b in between n and 2n. We can make use of nondeterminism to allow this as follows: for every a we put onto the stack, we can nondeterministically decide whether to consume one or two b before popping the a. If our NPDA chooses to consume one each time, we get a^n b^n. If it choose to consume two each time, we get a^n b^2n. If it chooses some of both, we get a number of b in between these extremes. We only accept when we exhaust the input with an empty stack.

Now, I changed the question a little bit(interchanged the powers of a and b). The language is now L={a^m b^n where n<=m<=2n}? How would this strategy change now if the powers are interchanged?

Answer 1

We can make use of nondeterminism to allow this as follows: for every a we put onto the stack, we can nondeterministically decide whether to consume one or two b before popping the a.

Just exchange a's and b's in this sentence and you should have your answer.

Hint: instead of putting a's on the stack, you put b's, and then "consume" one or two a's before popping.