A pushdown automation or a context-free grammar—which is more economical?

AbstractFor every pair of positive integers n and p, there is a language accepted by a real-time deterministic pushdown automaton with n states and p stack symbols and size O(np), for which every context-free grammar needs at least n2p+1 nonterminals if n>1 (or p non-terminals if n = 1). It follows that there are context-free languages which can be recognized by pushdown automata of size O(np), but which cannot be generated by context-free grammars of size smaller than O(n2p); and that the standard construction for converting a pushdown automaton to a context-free grammar is optimal in the sense that it infinitely often produces grammars with the fewest number of nonterminals possible