Length of Descriptions for DFA, NFA, CFG

We will be looking at the size of descriptions

 For DFAs and NFAs this is the number of states.

For CFG's we will assume they are in Chomsky Normal Form. So for this post CFG means CFG in Chomsky normal form. The length of a Chomsky Normal Form CFL is the number of rules.

1) It is known there is a family of languages L_n such that

DFA for L_n requires roughly 2^n states.

NFA for L_n can be done with roughly n states.

L_n =  (a,b)^* a (a,b)^n

Also note that there is a CFG for L_n with roughly n rules. (one can show this directly or by some theorem that goes from an NFA of size s to a CFG of size roughly s).

So L_n shows there is an exp blowup between DFAs and NFA's

2) It is known that there is a family of languages L_n such that

DFA for L_n requires roughly 2^n states

NFA for L_n requires roughly 2^n states

CFG for L_n can be done with roughly n rules

L_n = { a^{2^n}  }

So L_n shows there is an exp blowup between NFAs and CFGs.


3) Is there a family of languages L_n such that

NFA for L_n requires 2^{2^n} states

CFG for L_n can be done with roughly n rules.

The answer is not quite- and perhaps open.  There is a set of family of languages L_n such that for infinitely many n he above holds. These languages have to do with Turing Machines. In fact, you can replace

2^{2^n}} with any function f  \le_T  INF (so second level of undecidability).

For this blog this is NOT what we are looking for. (For more on this angle see here


4) OPEN (I think) Is there a family of langs L_n such that for ALL n

NFA for L_n requires 2^{2^n} (or some other fast growing function

CFG for L_n can be done with roughly n states (we'll take n^{O(1)})

5) OPEN (I think) Is there a family of langs L_n such that for ALL n
(or even for just inf many n)

DFA for L_n requires 2^{2^n}} states

NFA for L_n requires 2^n states and can be done in 2^n

CFG for L_n can be done with n rules.

(we'll settle for not quite as drastic, but still want to see DFA, NFA, CFG all
far apart).