Sizes of DFAs, NFAs, DPDAs, UCFG, CFGs, CSLs.

If A is a decider (e.g, DFA)  or generator (e.g., CFG) then L(A) is the language  that it decides or generates.

The following are well known:

L(DFA) = L(NDFA) ⊂ L(DPDA) ⊂ L(PDA) ⊂ L(CSL).

We are concerned with the  size of these devices. For a DFA and NDFA the size is
the number of states, for a DPDA, PDA the size is the sum of the stack alphabet and the number of states, and for CSL its the number of nonterminals.

If D and E are two classes of devices (e.g., DFAs and DPDAs) then a bounding function for (D,E)  is a function f such that if L is recognized by both a D-device and an E-device, and L is recognized by an E-device of size n, then it is recognized by a D-device of size ≤ f(n). We abbreviate b-fun

Readers of this column likely know that f(n)=2^n is a b-fun for (DFA,NFA) and prob know that this is tight. Below are some results that I suspect many readers don't know. Some of them  may be suitable for inclusion in an undergrad theory class. In what is below ≤ means Turing-Less-Than-Or-Equal.

1.  Stearns showed that f(n) = n^{n^{n^{O(n)}}} is a b-fun for (DFA,DPDA).
2.  Valiant improved this to double exp for a b-fun for (DFA,DPDA).
3.  Meyer and Fischer showed the 2^n lower bound for (DFA,NDFA). They also showed a lower bound of 2^{2^{O(n)}} for (DFA,DPDA). I think the question of closing the gap between Valiant's result and the Meyer-Fischer result is still open; however, if you know a ref please leave a comment.
4. Valiant showed that the if f is a b-fun for (DPDA,UCFG) then HALT ≤  f.
5. Schmidt showed that if f is a b-fun for (UCFG,CFG) then HALT ≤  f. 
6. Hartmanis showed that if f is a b-fun for (DPDA,PDA) then HALT ≤ f
7. Hay  showed that if f is a b-fun for (DPDA,PDA) then f is NOT computable-in-HALT. 
8. Beigel and Gasarch prove a general theorem from which they obtain the following: (a) if f is a b-fun  for (DPDA,PDA) then f ≤_INF. (It is easy to show that there exists a b-fun f ≤ INF for (DPDA,PDA) so the Turing degree is now precise), and (b) if f is a b-fun for (PDA,CSL) then SAME AS PART (a).

Results 3,4,5,6,7 can be restated in the following way--- we'll do result 6 as an example:

 If f  ≤  HALT then there exists infinitely many n such that there exists L_n such that  (a) L_n is DPDA, (b) there is a PDA for L_n of size n, (c) any DPDA for L_n is of size  at least f(n).

 Are there any ``for almost all n '' type bounds? There are but they are much weaker.  The following theorems are from the Beigel-Gasarch paper pointed to above.

1. For almost all n there exists a  cofinite (hence DPDA) L_n that has a PDA of size O(n) but any DPDA for it has size 2^2^{n^{Ω(1)}}. 
2. Same as point 1 but for PDA,CSL.

Both results 1,2 above use natural languages  in that they are not created for the sole purpose of proving the theorem, no diagonalization (my spell check says thats spelled wrong but I think its spelled right). Using a construction Beigel-Gasarch obtained (Meyer probably had the result 40 years earlier with a diff proof, see the Beigel-Gasarch paper  for historical details) that if f  ≤  HALT then for almost all n there is a lang L_n such that L_n has a CSL of size n but any PDA for it is of size at least f(n).