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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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$$
$$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.
$$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$$
$$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.
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.