[Overview] [Previous] [Next]

Formal Definition of NPDA

A dfa (or nfa) is not powerful enough to recognize many context-free languages because a dfa can't count. But counting is not enough -- consider a language of palindromes, containing strings of the form wwsuperscript R. Such a language requires more than an ability to count; it requires a stack.

A nondeterministic pushdown automaton (npda) is basically an nfa with a stack added to it.

We start with the formal definition of an nfa, which is a 5-tuple, and add two things to it:

We also need to modify delta, the transition function, so that it manipulates the stack.

A nondeterministic pushdown automaton or npda is a 7-tuple

M = (Q, sigma, gamma, delta, q0, z, F)

Copyright 1996 by David Matuszek
Last modified Mar 3, 1996