# How to draw NPDA for words whose number of b's is strictly more than that of a's but strictly less than twice the amount

I know that CFG for $$\{a^{m}b^{n}\mid m\leq n\leq 2m \}$$ is $$S\rightarrow ab/abb/aSb/aSbb$$ but I am not able to tweak it in such a way that it is strictly in between m and 2m and not equal to any of m or 2m. I want to draw PDA for the same.

For drawing the PDA what I did was to push non-deterministically 1 a and 2a's and popping them out for b one by one. How should I handle the edge case that it always doesn't push 1 a or not always 2 a's?

As you knew intuitively, you just missed the solution by a millimeter, which, however, may look like a mile away.

$$S\rightarrow aabbb/aSb/aSbb$$

The idea is simple. Since $$ab$$ and $$abb$$ should not be generated, what is the shortest or simplest word that can be generated?

Here is a sketch of a NPDA. When it reads the first $$a$$, it goes to state $$q_1$$. When it reads the second $$a$$, it goes to state $$q_2$$. Then every time if it reads one $$a$$, it will push one or two $$a$$'s nondeterministically onto the stack. Then when it reads the first $$b$$ it goes to state $$q_4$$. When it reads the second $$b$$ it goes to state $$q_5$$. When it reads the third $$b$$ it goes to state $$q_6$$. Then every time if it reads one $$b$$, it pops out one $$a$$ from the stack, staying at state $$q_6$$.

I will let you flesh out the details.

• For each $a$ that is read push either one or two $b$s on the stack and pop them again one by one while reading the $b$s. Reading at least two $a$s and not always pushing two $b$s (i.e. the edge cases) can be controlled by the states. – ttnick Dec 19 '18 at 23:01
• I misled myself into construction of a DPDA, which cannot be done. For NPDA, the construction is easy. – John L. Dec 20 '18 at 5:29
• What I did was to push non-deterministically 1 a, 2a's and popping them out for b one by one. How should I handle the edge case that it always doesn't push 1 a or not always 2 a's? – Amisha Bansal Dec 20 '18 at 6:36
• Use states to deal with them. For the first $a$, just go to state $q_1$ without changing the stack. For the second $a$ go to $q_2$ without changing the stack. Now we are prepared to push to the stack (but not if we see $b$ immediately). – John L. Dec 20 '18 at 6:55