Economy of description by parsers, DPDA's, and PDA's

Abstract

It is shown that there is a sequence of languages E1, E2,... such that every correct prefix parser (one which detects errors at the earliest possible moment, e.g., LR or LL parsers) for En has size 2cn, yet a deterministic PDA recognizing En exists and has size O(n2). There is another easily described sequence of languages N1, N2,... for which N has a nondeterministic PDA of size O(n2), but no deterministic PDA of size less than 2cn. It is shown moreover, that this latter gap can be made arbitrarily large for different sequences of languages.