[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:

is a finite set of symbols called the stack alphabet, and
z is the stack start symbol.

We also need to modify

, the transition function, so that it manipulates the stack.

A nondeterministic pushdown automaton or npda is a 7-tuple

M = (Q,

, q₀, z, F) where

Q is a finite set of states,
is a the input alphabet,
is the stack alphabet,
is a transition function,
q₀ Q is the initial state,
z is the stack start symbol, and
F Q is a set of final states.