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

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.

• Do you mean accepting state? The accept state is the only state, accepting on an empty stack. – Luke Mathieson Aug 15 '12 at 13:48
• What is the question here exactly? – Raphael Aug 16 '12 at 7:19

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). • The PDA definitions I know allow pushing of multiple symbols at once. The key here is the (relative to NFA) additional acceptance criterion "empty stack". Also, one can think of this construction as nondeterministic recursive descent parsing. – Raphael Aug 16 '12 at 7:23 • Yeah, I guess calling it an "abuse of notation" is a little harsh. though aesthetically, I think the one-symbol-at-a-time model is nicer, in the sense that it feels closer to a restricted Turing Machine. I blame having Sipser as a textbook as an undergraduate. (Of course it's really just a trivial change with some intermediate states) – Luke Mathieson Aug 16 '12 at 8:51 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)