3
$\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$
  • 1
    $\begingroup$ What are your thoughts? $\endgroup$ – Raphael Jan 28 '14 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 '14 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 '14 at 15:43
2
$\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$
  • $\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$ – yuri kilochek Jan 29 '14 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$ – Rick Decker Jan 29 '14 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 '14 at 0:23
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$
  • 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 '14 at 16:30
  • $\begingroup$ @MikeB. Then you should post your own answer! $\endgroup$ – Raphael Jan 28 '14 at 17:52
  • $\begingroup$ @Mike B. indeed you should, RE derivatives appear to be what I wanted. $\endgroup$ – yuri kilochek Jan 29 '14 at 8:14

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.