Deep pushdown automata

Deep pushdown automata

For access to this article, please select a purchase option:

Buy chapter PDF
(plus tax if applicable)
Buy Knowledge Pack
10 chapters for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
Handbook of Mathematical Models for Languages and Computation — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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.

Chapter Contents:

  • 15.1 Basic model
  • 15.1.1 Definitions and examples
  • 15.1.2 Accepting power
  • 15.1.3 Open problems
  • Generalization
  • 15.2 Restricted versions
  • 15.2.1 Preliminaries and definitions
  • 15.2.2 Results
  • 15.2.3 Open problems

Inspec keywords: formal languages; context-sensitive grammars; context-free grammars; pushdown automata

Other keywords: n-limited state grammars; deep pushdown automata; infinite language family hierarchy; context-sensitive grammars; DPDA; context-free grammars

Subjects: Automata theory; Formal languages and computational linguistics

Preview this chapter:
Zoom in

Deep pushdown automata, Page 1 of 2

| /docserver/preview/fulltext/books/pc/pbpc026e/PBPC026E_ch15-1.gif /docserver/preview/fulltext/books/pc/pbpc026e/PBPC026E_ch15-2.gif

Related content

This is a required field
Please enter a valid email address