[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 ww.
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 ,
the transition function, so that it manipulates the stack.
- is a finite set of
symbols called the stack alphabet, and
is the stack start symbol.
A nondeterministic pushdown automaton or npda
is a 7-tuple
M = (Q, , ,
, q0, z,
- Q is a finite set of states,
- is a the input
- is the stack alphabet,
- is a transition
Q is the initial state,
is the stack start symbol, and
- F Q is
a set of final states.
Copyright © 1996 by David Matuszek
Last modified Mar 3, 1996