132 Pushdown Automata 6.2 Conversion of a Context-Free Grammar to a Pushdown Automaton It is not difficult to construct a pushdown automaton on the basis of the given context- free grammar with the following steps: 1. 2. Create two states of the automaton (there will be no others)--initial state P and favorable state F. Create a transition rule P, , F, S, where S is the start symbol of the grammar. 3. Create a rule F, c, c F, for every terminal symbol c of the grammar. 4. Create a transition F, , A F, x for every rule of the grammar A x, where x is the usual right part, i.e., a string of terminal and nontermi- nal symbols. It is worth noting that stack symbols of such a machine are all terminal and all nonterminal symbols of the grammar. At first glance it may seem surprising that a context-free language can be rec- ognized by a machine containing only two states. However, before drawing any conclu-