# When a NPDA is constructed from CFG, how many internal states will be used for accepting any string from the grammar?

Options given were:

(a) 2 (b) 3 (c) 4 (d) 5

This question was a part of my assignment. I think the answer is 2 internal states - one start state and the other end state/acceptance state, but I am not sure whether it is correct or not. Please correct me if I am wrong. Thanks.

• I don't understand the question, so I'd say it's a bad question, or at least badly formulated. Tell your professor. Commented Mar 18, 2017 at 8:21

The construction is mentioned in wikipedia. We have single state $1$. For every grammar production $(A\to \alpha)$ add an pda instruction "expand" $(1,\epsilon,A,1,\alpha)$ which means "pop $A$ and push $\alpha$ without reading input". Additionally we have "match" instructions $(1,a,a,1,\epsilon)$ which means "when symbol $a$ is on top of the stack, we must read it from the input, while popping it from the stack". The initial stack symbol is $S$, the axiom of the grammar.
Use a new initial stack symbol $Z$ to mark the bottom of the stack. Just add two instructions, one to push $S$ on the stack $(1,\epsilon,Z,1,SZ)$, the other to move to the accepting state $f$ when the empty stack is reached $(1,\epsilon,Z,f,\epsilon)$.
This however assumes the automaton model that I was brought up with. Certain books do not agree, and consider PDA that start with an empty stack (brrr). In that case an additional state is used to start and push $Z$ onto the stack, so we need three states.