For what kinds of languages is min |NFA| = Ω(min |DFA|)?

Question

Consider a regular language $L$. Let $D(L)$ be a minimal DFA for $L$ and $N(L)$ be a minimal NFA for $L$ (minimal in the sense of the smallest possible number of states for an automaton that recognizes the given language). Write $|A|$ for the size (number of states) of the automaton $A$. In general, $|N(L)|$ can be a lot smaller than $|D(L)|$ (down to $\lg |D(L)|$, since determinization is exponential in the worst case).

I am interested in languages for which the minimal NFA is guaranteed to be at least a fraction of the size of the DFA: $|N(L)| \ge k |D(L)|$. What families of regular languages have this property? In other words, for what family of languages $(L_n)$ such that $|D(L_n)| = n$ is $|N(L_n)| = \Omega(n)$?

Answer 1

Perhaps this is too trivial to bear mentioning, but I'll mention it anyway: one class of languages comes to mind (although there may be much more interesting classes of languages than this which satisfy the property).

Consider a family of languages $\{\{\epsilon\}, \{w\}, \{ww\}, ..., \{w^n\}, ...\}$ where $w \in \Sigma^*$. A minimal NFA for the $n$th language will have $n|w|+1$ states (assuming no dead state), whereas a minimal DFA will have $n|w|+2$ states (assuming a single dead state). We have that $n|w|+1 = \Omega(n|w|+2)$.

We get another family by allowing each language to accept up to $n|w|$; this is the family $\{\{\epsilon, w, ww, ..., w^n\} \mid n \geq 0\}$. The automata for these languages are practically identical to the corresponding automata from the other family, except these have more accepting states.

These happen to be families of finite languages. We could, of course, get a family of infinite languages as follows: $\{\{w^nw^*\} \mid n \geq 0\}$.

Consider any family of languages which consist of a single word. For any such language, the ratio of $|\min DFA|$ to $|\min NFA|$ will be less than $2$, so such a family of languages must satisfy the property. Since there are countably many finite strings over any alphabet, and since we're considering any possible subset thereof, we get an uncountable number of language families in this manner.

FWIW, to get these examples, my thinking was that we're looking for languages that involve doing something which an NFA can't do much better than a DFA. Accepting some random string, and nothing else, is notable in this regard. I guess more generally, there's an informal notion of "straightforwardness of the DFA" that seems to be related to what's being asked.

You know, come to think of it, I think we can generalize this a bit more: any family of languages with the following form should work: $L_n = \{s_0s_1...s_i\}L$ for $n \geq 0$, where $L$ is any regular language and $s_n$ is any finite string. Suppose for $L$ that $|\min DFA| = x$ and $|\min NFA| = y$. Then the family $L_n$ should always have $|\min DFA| / |\min NFA| \leq x/y$.

I don't know whether this is pertinent, interesting or useful, but I thought if nothing else this might revive the question.