While the ordinary pushdown lists can be modified only on their tops, deep pushdown lists, as their name suggests, can be modified under them. Accordingly, while the ordinary versions of pushdown automata can expand only the topmost pushdown symbols, deep pushdown automata (DPDAs) can make expansions deeper in their pushdown lists; otherwise, they both work identically. This chapter proves that the power of DPDAs is similar to the generative power of regulated context-free grammars without erasing rules. Indeed, just like these grammars, DPDAs are stronger than ordinary pushdown automata but less powerful than context-sensitive grammars. More precisely, they give rise to an infinite hierarchy of language families coinciding with the hierarchy resulting from n-limited state grammars. The chapter is divided into two sections. The former introduces the basic versions of DPDAs. The latter places some natural restrictions on them.
Deep pushdown automata, Page 1 of 2
< Previous page Next page > /docserver/preview/fulltext/books/pc/pbpc026e/PBPC026E_ch15-1.gif /docserver/preview/fulltext/books/pc/pbpc026e/PBPC026E_ch15-2.gif