7
$\begingroup$

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)$?

$\endgroup$
  • $\begingroup$ Intuitively it seems clear that the languages this characterizes are those where you can't gain anything complexity-wise by using nondeterminism. No idea what graspable property that might relate to, though. $\endgroup$ – G. Bach Sep 12 '13 at 18:15
  • $\begingroup$ I am afraid that your question does not make any sense as stated, since the $\Omega$ notation is only defined for functions, while in your question, you are considering only one language. $\endgroup$ – J.-E. Pin Sep 12 '13 at 19:48
  • $\begingroup$ @J.-E.Pin While you're right, his question makes sense if you ignore the sentence that starts "Let us suppose" and consider the last sentence to be in reference to the family of languages for which it holds. $\endgroup$ – G. Bach Sep 12 '13 at 20:18
  • 1
    $\begingroup$ Based on my understanding of the comments, the question is "for which families of languages does $|\min NFA| = \Omega(|\min DFA|)$?" Is this correct? $\endgroup$ – Patrick87 Sep 12 '13 at 23:21
  • 3
    $\begingroup$ The $\Omega$ notation only makes sense when $n$ tends to $\infty$. A possible simpler formulation would be: given a constant $c$, what is the class $\mathcal{L}_c$ of all regular languages satisfying $\min |DFA| \leqslant c \min |NFA|$. $\endgroup$ – J.-E. Pin Sep 13 '13 at 7:21
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.