3.2. One-Turn Pushdown Automata

It will be shown in the next chapter, that the class of pushdown automata accepts exactly the class of context-free languages (Section 4.6). The class of linear languages can be recognized by a class of special pushdown automata, called one-turn pushdown automata. We will present these automata in detail in Subsection 4.6.4., when we are familiar with the concept of pushdown automata.