1
$\begingroup$

Given $A_1$ - DFA with $n$ states, $A_2$ - NFA with $m$ states (both over the same alphabet - $\Sigma$). What's the state complexity, i.e. an upper bound for the amount of states of the minimal DFA, recognizing the language $L(A_1)\setminus L(A_2)=L(A_1) \cap(\Sigma^*\setminus L(A_2))$.

What I thought of: evaluate the state complexity of $\Sigma^*\setminus L(A_2)$ (hypothesis: $2^m$). Why? Because an upper bound of $2^m$ can be obtained for a DFA to accept the language of $A_2$. It's also known that the state complexity of the completion $\Sigma^*\setminus L(A_{min})$ is $k$, where $A_{min}$ is an arbitrary minimal $DFA$ with $k$ states. Therefore we can evaluate the upper bound of the minimal DFA, recognizing $L(A_1) \cap(\Sigma^*\setminus L(A_2))$ as $n2^m$ (the state complexity of the intersection is simply the product of states).

$\endgroup$
0
1
$\begingroup$

This is correct, and moreover it is tight for $n = 1$, even for a binary alphabet (but not for a unary alphabet!). Indeed, it is well-known that there are language accepted by $m$-state NFAs which require $2^m$ states for a DFA. Since the DFA complexity of a language and its complement coincide, taking $A_1 = \Sigma^*$ we obtain a tight example with $n = 1$ and any $m$.

It is an interesting question whether the bound is tight for all $n$. This is likely the case if we take for $L(A_1)$ the language $(\Sigma^n)^*$.

$\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.