Relative succinctness of NFAs and regular expressions

Question

What is known about the succintness of NFAs, relative to regular expressions?

In order to clarify the question, let me explain what I know. The regular languages can be characterized by any of the following:

1. A language is regular iff it can be recognized by an NFA.
2. A language is regular iff it can be recognized by a DFA.
3. A language is regular iff it can be defined by an MSO formula.
4. A language is regular iff it can be described by a regular expression.

The family of languages $(\{w\in\{0,1\}^* \mid |w|>n, w_{|w|-1-n}=0\})_{n\in\omega}$ has NFAs with $n+1$ states. For DFAs, there is a lower bound of $2^n$ states. This family exemplifies that the translation from NFAs to DFAs necessarily incurs a worst-case exponential explosion of size.

In the other direction, there is no explosion, because each DFA is an NFA. Together, we can say that NFAs are exponentially more succinct than DFAs.

A similar result holds for the comparison of automata (either NFAs or DFAs) to MSO formulae: The formulae are non-elementarily more succinct.

I am aware that the translation from regular expressions to NFAs is linear and that there is an exponential translation in the other direction. Now to the actual question: Is it known that an exponential blowup cannot be avoided? What NFAs (or even DFAs) witness this? What techniques are used to prove non-existence of short regular expressions?

This question leads me to assume that divisibility languages are witnesses. That was what prompted the present question.

Answer 1

DFAs can be exponentially more succinct than regular expressions. A simple example is the language of all words over $\{a,b\}$ in which the number of $a$s and the number of $b$s are each divisible by $n$. This is accepted by a DFA of size $n^2$, but requires a regular expression of length $2^{\Omega(n)}$. For proof, see Example 23 in the survey From finite automata to regular expressions and back by Gruber and Holzer.

Gruber and Holzer improved this in their paper Tight bounds on the descriptional complexity of regular expressions, also mentioned in their survey (Theorem 24 of the survey). In fact, they prove an even stronger result (Theorem 8 of the paper): there is a language described by a regular expression of length $O(n)$ whose complement requires a regular expression of length $2^{2^{\Omega(n)}}$. (A regular expression of length $O(n)$ corresponds to an NFA having $O(n)$ states and so to a DFA having $2^{O(n)}$ states, whose complement has the same number of states.) The regular expression with this wondrous properties, over the alphabet $\{0,1,\$\}$, is $$ (0+1)^{\geq 1} + (\epsilon + \Sigma^*\$)\bigl((0+1)^{\leq 4n-1}\$ + (0+1)^{\geq 4n+1}\bigr)\Sigma^* \\ + \Sigma^*\$(0+1)^{3n}(0+1)^*0\Sigma^{n+1}1\Sigma^* \\ + \Sigma^*\$(0+1)^{3n}(0+1)^*1\Sigma^{n+1}0\Sigma^* \\ + \Sigma^*\$(0+1)^*0\Sigma^{2n}1\Sigma^* \\ + \Sigma^*\$(0+1)^*1\Sigma^{2n}0\Sigma^* $$ We can even obtain an example over the binary alphabet $\{a,b\}$ using the homomorphism $$ 0 \mapsto abbb, \quad 1 \mapsto aabb, \quad \$ \mapsto aaab. $$

The way all of these results are proved is via the concept of star height: a language of star height $h$ requires a regular expression of length $2^{\Omega(h)}$. Unfortunately lower bounds on the star height are rather difficult to establish, so instead one uses the more manageable cycle rank, a theorem of McNaughton identifying the two for a class of languages known as bideterministic. (For more details, consult either of the sources cited above.)