[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, , , , q0, z, F)
where
• Q is a finite set of states,
• is a the input alphabet,
• is the stack alphabet,
• is a transition function,
• q0 Q is the initial state,
• z is the stack start symbol, and
• F Q is a set of final states.