Pushdown automata

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.

Pushdown automata represent, in essence, finite automata extended by potentially infinite stacks, commonly referred to as pushdown lists or, more briefly, pushdowns. In this chapter, we demonstrate that these automata are as powerful as context-free grammars, discussed in the previous chapter. This chapter is divided into four sections. First, Section 7.1 defines pushdown automata. Then, Section 7.2 stablishes the equivalence between them and context-free grammars. Section 7.3 introduces three ways of accepting languages by these automata. Finally, Section 7.4 narrows its attention to the deterministic versions of pushdown automata and demonstrates that they are less powerful than their nondeterministic versions.

Chapter Contents:

  • 7.1 Pushdown automata
  • 7.2 Pushdown automata and context-free grammars are equivalent
  • 7.3 Three types of acceptance by pushdown automata
  • 7.4 Determinism

Inspec keywords: context-free grammars; pushdown automata

Other keywords: context -free grammars; pushdown automata

Subjects: Automata theory; Formal languages and computational linguistics

Preview this chapter:
Zoom in

Pushdown automata, Page 1 of 2

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

Related content

This is a required field
Please enter a valid email address