When generating a PDA from a CFG do I have a receiving state?

Question

Thw Wikipedia article on Pushdown automata doesn't explain what the receiving state is for the generated PDA it just states that there is but one state.

Answer 1

Assuming that you mean accept state when you say receiving state, the construction given in the wikipedia article has one accept state, being the only state in the machine. It accepts when you reach the end of the input with an empty stack. However, the construction used there requires a slight abuse of notation, as you need the starting symbol from the grammar to be pushed to begin with, and you have to be able to push more than one symbol at a time. This isn't so bad, but a more detailed construction makes the conversion more obvious.

The basic approach is to simulate the CFG using the PDA, informally it reads symbols off the stack, if it's a nonterminal, it replaces it with its production, if it's a terminal, it matches it off the input. The input alphabet for the PDA is the same as the CFG, the stack alphabet is the input alphabet plus the set of nonterminals in the CFG and the end of stack symbol.

The basic backbone of the PDA is: Where $\$$ is the special end of stack symbol, and $S$ is the start symbol of the grammar.

The "production rules" transition represents a bunch of loops that simulate each production of the grammar. Given a production $X \rightarrow \chi_{1}\ldots\chi_{n}$ where the $\chi_{i}$'s are either terminals or nonterminals, we add a loop starting and ending at $q_{3}$ that looks like: Note that I've opened the loop, and the first and last state are the same.

The last past is the "terminal rules" loop, which represent a bunch of loops (one for each terminal symbol), that match terminals pushed onto the stack by the productions to terminals in the input:

So hopefully you can see how the simulation works, the PDA literally walks through the steps of the CFG, sticking terminals and nonterminals on the stack, replacing nonterminals with their productions, and matching terminals off the input. Then it can only reach the accept state if you can match the entire input (and hence there must be some series of grammar rules that get you there).

Answer 2

There are several equivalent PDA models:

1. In one model, "By accepting state", the PDA accepts if at the end of processing the input, the automaton is in an accepting state.
2. In another model, "By empty stack", the PDA accepts if at the end of processing the input, the stack is empty (regardless of the state the PDA ends at)
3. Although the two above models are enough, sometimes people combine them to a model that accepts "By stack and state", in which the PDA accepts only if at the end of the computation, the automaton is at an accepting state, and the stack is empty.

The construction you mentioned in your question (the one that appears on the Wiki page) has only one state. Clearly, this means we cannot be in the first model (otherwise, the PDA will always accept either $\Sigma^*$ or $\emptyset$, because there's only one state which is either final or not). Therefore, the model implied in the wiki page is "by emptying the stack". (or "By state and stack", assuming the single-state is accepting)

Indeed, the PDA uses the grammar to non-deterministically derive the input word on the stack, and at the same time, on the fly, checks that the input and the derived word on the stack are equal (popping form the stack any checked letter). If the non-deterministic process derived exactly the input word, this process succeeds, and at the end of the computation the stack will be empty and the PDA will accept (Alternatively, there exists a computation path that will accept—the one in which the input word is derived on the stack). On the other hand, if the input word cannot be generated by the grammar, then no computation path can generate the input word on the stack, and the computation (any computation path) is bound to reject.