Direct construction of NFA for the difference of regular languages

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?

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.

StackExchange Computer Science Q#20042, answer score: 3