On reducing the number of stack symbols in a PDA

Two transformations are presented which, for any pushdown automaton (PDA)M withn states andp stack symbols, reduce the number of stack symbols to any desired numberp greater than one. The first transformation preserves deterministic behavior and produces an equivalent PDA witho(np/p) states. The second construction, using a technique which introduces nondeterminism, produces an equivalent PDA withO(np/p) states. Both transformations are essentially optimal, the former among determinism-preserving transformations, the latter among all transformations.This research was supported in part by the National Science Foundation under Grants MCS 76-10076 and MCS 76-10076A01 and by the Stiftung Volkswagenwerk under Grant No. II/62 325.