On reducing the number of states in a PDA

A transformation is presented which converts any pushdown automaton (PDA)M₀ withn₀ states andp₀ stack symbols into an equivalent PDAM withn states and n₀/n²p₀ stack symbols into an equivalent ofn, 1n₀. This transformation preserves realtime behavior but not derterminism. The transformation is proved to be the best possible one in the following sense: for each choice of the parametersn₀ + 1 stack symbols for any desired value realtime PDAM₀ such that any equivalent PDAM (whether realtime or not) havingn states must have at least (n₀/n)² p₀ stack symbols. Furthermore, the loss of deterministic behavior cannot be avoided, since for each choice ofn₀ andp₀, there is a deterministic PDAM₀ such that no equivalent PDAM with fewer states can be deterministic.This research was supported in part by the National Science Foundation under Grants MCS76-10076 and MCS76-10076A01.