We assert without proof that any npda can be transformed into an equivalent npda that has the following form:

- The npda has only one final state, which it enters if and only if the stack is empty;
- All transitions have the form
(q, a, A) = {c where each c_{1}, c_{2}, c_{3}, ...}_{i}has one of the two forms- (q
_{j}, ) - (q
_{j}, BC)

- (q

Copyright © 1996 by David Matuszek

Last modified Mar 18, 1996