http://iet.metastore.ingenta.com
1887

## Pushdown automata

• Author(s):
• DOI:

$16.00 (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.

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:

Handbook of Mathematical Models for Languages and Computation — Recommend this title to your library

## Thank you

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:

Other keywords:

Preview this chapter:

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

content/books/10.1049/pbpc026e_ch7
pub_keyword,iet_inspecKeyword,pub_concept
6
6
This is a required field