On the sizes of DPDAs, PDAs, LBAs

There are languages A such that there is a Pushdown Automata (PDA) that recognizes A which is much smaller than any Deterministic Pushdown Automata (DPDA) that recognizes A. There are languages A such that there is a Linear Bounded Automata (Linear Space Turing Machine, henceforth LBA) that recognizes A which is much smaller than any PDA that recognizes A. There are languages A such that both A   and A‾ are recognizable by a PDA, but the PDA for A   is much smaller than the PDA for A‾. There are languages A1,A2A1,A2 such that A1,A2,A1∩A2A1,A2,A1∩A2 are recognizable by a PDA, but the PDA for A1A1 and A2A2 are much smaller than the PDA for A1∩A2A1∩A2. We investigate these phenomena and show that, in all these cases, the size difference is captured by a function whose Turing degree is on the second level of the arithmetic hierarchy.Our theorems lead to infinitely-many-n results. For example: for-infinitely-many-n   there exists a language AnAn recognized by a DPDA such that there is a small PDA for AnAn, but any DPDA for AnAn is very large. We look at cases where we can get all-but-a-finite-number-of-n results, though with much smaller size differences.