5
$\begingroup$

Let $A$ and $B$ be regular languages. Let $C$ be their difference, i.e $C = B \setminus A$.

Given NFAs for $A$ and $B$, is it possible to directly construct an NFA for $C$ without (implicitly or explicitly) converting them to DFAs first?

$\endgroup$
3
  • 1
    $\begingroup$ What are your thoughts? $\endgroup$
    – Raphael
    Jan 28, 2014 at 17:53
  • $\begingroup$ What's wrong with converting them to DFAs? Why have you rejected that solution? This site is best when your question arises from some real problem you actually face. As it stands, this is not a real problem. A real problem would be, for example, "converting to DFAs can cause exponential blowup, so is there an algorithm that does not have exponential blowup?" Basically, a real problem would state requirements, not just say you're looking for anything other than algorithm X. As it stands you haven't listed any requirements, so the problem is not well-posed. $\endgroup$
    – D.W.
    Jan 29, 2014 at 2:19
  • $\begingroup$ if you want an automaton representing $C$, and you don't really care if it's a NFA, you can compute quickly an alternating automaton of polynomial size for $C$. $\endgroup$
    – Denis
    Jan 29, 2014 at 15:43

3 Answers 3

3
$\begingroup$

The short answer is "yes".

Probably the easiest way to explain it is with an example; turning this into a formal algorithm should be straightforward.

The first NFA, $M$, accepts the language $(a\cup b)^*$:

$$q_0 = \epsilon \cup a q_0 \cup b q_0$$

with the start state being $q_0$.

This is probably not notation that you're used to, but the reason for using this will become clear soon; it's basically saying the same thing as the context-free grammar:

$$ S \rightarrow \epsilon $$ $$ S \rightarrow a S $$ $$ S \rightarrow b S $$

You can see how this is also a description of a NFA. Each term on the right-hand side is either a transition $aq_i$, which means read an $a$ and go to state $q_i$, or $\epsilon$ which means that the state is a final state.

The second NFA, $M$, accepts the language $(a\cup b)^*aa(a\cup b)^*$, that is, any string which contains $aa$. The start state is $q_1$; I've used unique state names for reasons that will become obvious in a moment. I deliberately picked an NFA which has some nondeterminism just to show that this works for that case.

$$q_1 = a q_1 \cup b q_1 \cup a q_2$$ $$q_2 = a q_3$$ $$q_3 = \epsilon \cup a q_3 \cup a q_3$$

We would like to construct a NFA which accepts the language:

$$Q_0 = q_0 \setminus q_1$$

expanding one level gives:

$$Q_0 = (\epsilon \cup a q_0 \cup b q_0) \setminus (a q_1 \cup b q_1 \cup a q_2)$$ $$ = \epsilon \cup a (q_0 \setminus (q_1 \cup q_2)) \cup b (q_0 \setminus q_1)$$ $$ = \epsilon \cup a Q_1 \cup b Q_0$$

where:

$$Q_1 = q_0 \setminus (q_1 \cup q_2)$$

Note that we already had a state which handled the $b$ transition correctly. For the $a$ transition, we didn't, so we introduced one.

We continue:

$$Q_1 = q_0 \setminus (q_1 \cup q_2)$$ $$= (\epsilon \cup a q_0 \cup b q_0) \setminus (a q_1 \cup b q_1 \cup a q_2 \cup a q_3)$$ $$= \epsilon \cup a (q_0 \setminus (q_1 \cup q_2 \cup q_3)) \cup b (q_0 \cup q_1)$$ $$= \epsilon \cup a Q_2 \cup b Q_0$$

where:

$$Q_2 = q_0 \setminus (q_1 \cup q_2 \cup q_3)$$

continuing again, going a little more slowly this time:

$$Q_2 = q_0 \setminus (q_1 \cup q_2 \cup q_3)$$ $$= (\epsilon \cup a q_0 \cup b q_0) \setminus ((a q_1 \cup b q_1 \cup a q_2) \cup (a q_3) \cup (\epsilon \cup a q_3 \cup b q_3))$$ $$= a (q_0 \setminus (q_1 \cup q_3)) \cup b (q_0 \setminus (q_1 \cup q_3))$$ $$= a Q_2 \cup b Q_2$$

Note that we used the fact that $\epsilon \setminus \epsilon = \varnothing$.

So in summary, we have the following NFA with start symbol $Q_0$:

$$Q_0 = \epsilon \cup a Q_1 \cup b Q_0$$ $$Q_1 = \epsilon \cup a Q_2 \cup b Q_0$$ $$Q_2 = a Q_2 \cup b Q_2$$

You can verify for yourself that this accepts the language.

There are several things to notice about this.

First off, the process must terminate; there are only a finite number of possible transition states which could be created.

Secondly, the running time could be exponential in the worst case; each transition state is of the form $\bigcup_i q_i \setminus \bigcup_j q_j$ where the left-hand side of the set minus is a subset of the states from the first machine and the right-hand side is the same for the second machine. There is a finite number of such subsets, but there could be exponentially many in general, and sometimes there will be. And the reason is...

...the final answer is a DFA! It's not hard to see that this will always be the case. Your question only asked for a method that didn't convert the two NFAs to DFAs first, and you never said anything about not constructing a DFA for the final answer.

Basically what we've done here is folded the NFA-to-DFA conversion algorithm together with the DFA difference algorithm, so one algorithm does both. I think this satisfies the requirements of your question.

$\endgroup$
3
  • $\begingroup$ Thanks for the effort of writing that down, but you could have just mentioned existence of RE derivatives, and that they can be used for direct DFA construction. $\endgroup$ Jan 29, 2014 at 8:08
  • $\begingroup$ +1. This construction can often be very useful. It's unfortunate that it's rarely (in my experience) taught in intro theory courses. $\endgroup$ Jan 29, 2014 at 14:31
  • $\begingroup$ yuri, I could have mentioned the existence of RE derivatives, but surely that's only tangentially relevant to the question? Taking the difference of REs is best done via derivatives, I agree, but taking the difference of NFAs by converting to REs first seems even less efficient than converting to DFAs first. $\endgroup$
    – Pseudonym
    Jan 30, 2014 at 0:23
1
$\begingroup$

Let $N_A$ and $N_B$ be NFAs for the languages $A$ and $B$, respectively. Note that $B\setminus A = B\cap \overline{A}$. Hence, to obtain an NFA $N_C$ for $C = B\cap \overline{A}$, one needs to complement $N_A$, but you don't have to complement $N_B$ as the product construction for intersection can be easily adapted to nondeterministic automata. To sum up, the best you can do is the following: determinize $N_A$ and turn it into a complementing DFA $D$ for $\overline{A}$, and then use a product construction of $N_B$ and $D$ to get an NFW $N_C$ for $ L(N_B)\cap L(D) = B\cap \overline{A}$.

Note that there is no way around determinizing $N_A$ as if you fix $B$ to $\Sigma^*$, then $B\setminus A = \overline{A}$, and the best known way to complement NFAs is by first determinizing them. The latter is justified by examples in which there is an exponential gap between the NFA complexity of a language and its complement. For example, see here and here.

$\endgroup$
0
$\begingroup$

There's no known way to complement an NFA without first converting to a DFA, which is a simpler operation than what you need here: complementing and then intersecting.

$\endgroup$
3
  • 1
    $\begingroup$ Thats not entirely true: You can convert the NFA into a regular expression, and you can construct an NFA that accepts the complement of the language of a regular expression. (Apparently with Brzozowski derivatives, see Pseudonym's comments in cs.stackexchange.com/questions/19686 ). Its just not very straight-forward. $\endgroup$
    – Mike B.
    Jan 28, 2014 at 16:30
  • $\begingroup$ @MikeB. Then you should post your own answer! $\endgroup$
    – Raphael
    Jan 28, 2014 at 17:52
  • $\begingroup$ @Mike B. indeed you should, RE derivatives appear to be what I wanted. $\endgroup$ Jan 29, 2014 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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