# Designing a PDA without using CFG -> PDA for the language $\{ a^nb^m | n \le m \le 2n \}$

$$L= \{ a^nb^m | n \le m \le 2n \}$$

As you may recall, I posted a question a few hours ago about designing a PDA for a language similar to the one I have now. I have seen that the easiest way to construct it is to define a CFG for the language, and then transform it to non-deterministic PDA which accepts strings by empty stack.

However, for this exercise, we have been forbidden to do that. We have to construct an automaton which accepts strings with a final state. Here's my proposed solution:

Here's my reasoning. If I was to construct a context-free grammar, the rules of production would be $$S \to aSb | aSbb|\epsilon$$. I tried to do something similar here by putting $$a$$ and $$aa$$ on the stack for the same input symbol and the same popped symbol from the stack, creating a non-deterministic PDA.

My question is: Am I correct to assume this is a correct interpretation of non-determinism?

• A possible approach to writing this PDA was suggested by Yuval in cs.stackexchange.com/a/147932/4287 , for a bound of $3n$ rather than $2n$, but that is similar. Jun 9, 2022 at 23:21

## 1 Answer

Your language is NCFL. Your design of NPDA is perfectly right. And in state $$q_0,q_1$$ and $$q_2$$ transitions makes your diagram NPDA. You accepts your strings by final state that is $$q_3.$$ If you want to accept by empty stack(without final state) then no need to move and create the new state $$q_3.$$ You just give the transition $$(\epsilon,A/\epsilon)$$ in state $$q_2$$ that is $$\delta(q_2,\epsilon,A)=(q_2,\epsilon)$$ , then the stack will be empty.

• Thank you very much! This is very important to me because yesterday I thought that the only method to solve the $n \le m \le x \cdot n, x \in \mathbb{N}$ is by doing CFG -> PDA. Jun 10, 2022 at 7:30