140 Pushdown Automata chapter. Therefore, let's postpone, for now at least, the topic of deterministic pushdown automata (we will return to it) and proceed to a discussion of the parsing problem, as fol- lows in the next chapter. 6.7 Conclusions · A pushdown automaton represents a device that is powerful enough for recognition of any context-free language. But the recognition power of pushdown automata is limited to context-free languages. · Proofs of the previous statement are constructive: there exist the algorithms for converting a context-free grammar to a pushdown automaton and vice versa. · Nondeterministic pushdown automata are hard to emulate on a computer. · Deterministic pushdown automata are capable of recognizing only some subsets of context-free languages. The languages of these sub- sets are called deterministic (provided that the pushdown automaton