2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I don't understand the question, so I'd say it's a bad question, or at least badly formulated. Tell your professor. $\endgroup$ Mar 18 '17 at 8:21
2
$\begingroup$

The answer depends.

For every CFG we can construct an equivalent PDA with empty stack acceptance that has just a single state.

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.

If we instead want final state acceptance then we need to distinguish a final state, so it is necessary to use two states.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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