3
$\begingroup$

I have a task to determine the upper bound of states in the Minimal Deterministic Finite Automata that recognizes the language: $ L(A_1) \backslash L(A_2) $, where $ A_1 $ is a Deterministic Finite Automata (DFA) with $n$ states and $A_2$ is Non-deterministic Finite Automata (NFA) with $m$ states.

The way I am trying to solve the problem:

  1. $ L(A_1) \setminus L(A_2) = L(A_1) \cap L(\Sigma^* \backslash L(A_2))$, which is language, that is recognised by an automaton $L'$ with $nm$ states.
  2. Determinization of $L'$ which has $(nm)^2$ states and it is the upper bound of states.

Am I right?

$\endgroup$
  • $\begingroup$ We discourage "check my answer" questions, as they call for an answer that is either yes or no. Neither is likely to be useful to others in the future. We'd prefer that you isolate a conceptual question that will be useful to others again in the future. $\endgroup$ – D.W. Jun 3 at 4:40
3
$\begingroup$

This is wrong. Determinization of an NFA with $r$ states could result in a DFA with up to $2^r$ states. Therefore your argument actually gives an upper bound of $$2^{nm}. $$ This can be improved if you switch the order of operations. If you first convert your NFA to a DFA and only then apply the product construction, then you get the better bound $$ n2^m. $$

This bound is tight for infinitely many values of $n,m$. Consider the language $L_2$ of all words over $\Sigma^*\{\sigma_1,\ldots,\sigma_2\}$ that do not contain all letters. There is an NFA for $L_2$ (with multiple initial states) using only $m$ states. However, any NFA for $\overline{L_2}$ needs to contain at least $2^m$ states. Since $\overline{L_2} = \Sigma^* \setminus L_2$ and $\Sigma^*$ can be accepted by a single-state DFA, we see that the bound above is optimal.

You can probably show that the bound is tight for (practically) all $n,m$ by slightly modifying the above construction, replacing $\Sigma^*$ with $(\Sigma^n)^*$.

| cite | improve this answer | |
$\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.