How to find the intersection of two NFA

Question

In DFA we can do the intersection of two automata by doing the cross product of the states of the two automata and accepting those states that are accepting in both the initial automata. Union is performed similarly. How ever although i can do union in NFA easily using epsilon transition how do i do their intersection?

templatetypedef · Accepted Answer · 2017-11-14T21:18:12.603

7

You can use the cross-product construction on NFAs just as you would DFAs. The only changes are how you'd handle ε-transitions. Specifically, for each state (q_i, r_j) in the cross-product automaton, you add an ε-transition from that state to each pair of states (q_k, r_j) where there's an ε-transition in the first machine from q_i to q_k and to each pair of states (q_i, r_k) where there's an ε-transition in the second machine from r_j to r_k.

Alternatively, you can always convert the NFAs into DFAs and then compute the cross product of those DFAs.

Hope this helps!

edited Nov 14 '17 at 21:18

answered Feb 09 '14 at 17:32

templatetypedef

362,284
104
897
1,065

so there is no easy method like just adding epsilon as in the union case? – Aditya Nambiar Feb 09 '14 at 17:47
@AdityaNambiar- Not to the best of my knowledge. – templatetypedef Feb 09 '14 at 17:48
An other answer here raised a concern about missing "simultaneous ε-transitions", where both machines make an ε-transition at the same time. I haven't found any trouble yet with omitting them since those transitions can be done in several steps anyway, but maybe there is some weird edge case. Could you clarify this? – harold Nov 14 '17 at 21:05
@harold I don't believe you need to explicitly handle this case, since you could imagine following an ε-transition in the first machine followed by taking an ε-transition in the second machine as a chain of two εs even if the above construction doesn't directly include a transition from the initial pair to the destination pair. – templatetypedef Nov 14 '17 at 21:19
@AdityaNambiar if you want some easy method like the one for the union case, you need alternating automata instead of nondeterministic ones. It will also allow you to perform efficiently language complement (and hence all the useful boolean operations, e.g. inclusion). The trouble is again in harder simulation and analysis of AFA. – pallly Apr 04 '19 at 10:54
[Never mind, I retract my comment.] – xFioraMstr18 Mar 10 '22 at 03:40

score 3 · Answer 2 · edited Nov 04 '14 at 16:31

3

We can also use De Morgan's Laws: A intersection B = (A' U B')'

Taking the union of the compliments of the two NFA's is comparatively simpler, especially if you are used to the epsilon method of union.

edited Nov 04 '14 at 16:31

Chris Forrence

10,042
11
48
64

answered Nov 04 '14 at 14:26

aneena

187
1
2
13

3

Hmm... how do you take the negation of an NFA, other than by turning it into a DFA first? – Stefan May 06 '15 at 21:18
While this answer is correct, the complement does require transforming to a DFA with powerset construction - for all three complements, even, since the epsilon method creates another NFA. Exponential worst-case at least. (Potentially `2^2^n`, but I am unsure if that case actually exists.) – Christoph Burschka Apr 14 '20 at 13:42

score 2 · Answer 3 · edited Mar 14 '22 at 01:26

2

There is a huge mistake in templatetypedef's answer.

The product automaton of L1 and L2 which are NFAs :

New states Q = product of the states of L1 and L2.

Now the transition function:

a is a symbol in the union of both automatons' alphabets

delta( (q1,q2) , a) = delta_L1(q1 , a) X delta_L2(q2 , a)

which means you should multiply the set that is the result of delta_L1(q1 , a) with the set that results from delta_L2(q1 , a).

The problem in the templatetypedef's answer is that the product result (qk ,rk) is not mentioned.

edited Mar 14 '22 at 01:26

xFioraMstr18

117
6

answered Apr 15 '15 at 04:35

KFkf

175
13

Note that harold and templatetypedef have addressed this concern in the thread under templatetypedef's answer, and this does not seem to be an issue after all. – MattS Sep 19 '20 at 04:08

score 1 · Answer 4 · edited Mar 14 '22 at 11:05

Probably a late answer, but since I had the similar problem today I felt like sharing it. Realise the meaning of intersection first. Here, it means that given the string e, e should be accepted by both automata.

Consider the folowing automata:

m1 accepting the language {w | w contains '11' as a substring}
m2 accepting the language {w | w contains '00' as a substring}

Intuitively, m = m1 ∩ m2 is the automaton accepting the strings containing both '11' and '00' as substrings. The idea is to simulate both automata simultaneously.

Let's now formally define the intersection.

m = (Q, Σ, Δ, q0, F)

Let's start by defining the states for m; this is, as mentioned above the Cartesian product of the states in m1 and m2. So, if we have a1, a2 as labels for the states in m1, and b1, b2 the states in m2, Q will consist of following states: a1b1, a2b1, a1b2, a2b2. The idea behind this product construction is to keep track of where we are in both m1 and m2.
Σ most likely remains the same, however in some cases they differ and we just take the union of alphabets in m1 and m2.
q0 is now the state in Q containing both the start state of m1 and the start state of m2. (a1b1, to give an example.)
F contains state s IF and only IF both states mentioned in s are accept states of m1, m2 respectively.
Last but not least, Δ; we define delta again in terms of the Cartesian product, as follows: Δ(a1b1, E) = Δ(m1)(a1, E) x Δ(m2)(b1, E), as also mentioned in one of the answers above (if I am not mistaken). The intuitive idea behind this construction for Δ is just to tear a1b1 apart and consider the states a1 and b1 in their original automaton. Now we 'iterate' each possible edge, let's pick E for example, and see where it brings us in the original automaton. After that, we glue these results together using the Cartesian product. If (a1, E) is present in m1 but not Δ(b1, E) in m2, then the edge will not exist in m; otherwise we'll have some kind of a union construction.

Aren't you supposed to define Δ to take in a character (an element of Σ), not an edge? Also, you could write "If (a1, E) is present in m1 but not Δ(b1, E) in m2" in a more parallel way (e.g. "If (a1, E) is present in m1 but (b1, E) is not present in m2"). — xFioraMstr18, Mar 10 '22 at 03:47

score -2 · Answer 5 · answered Feb 13 '14 at 15:41

An alternative to constructing the product automaton is allowing more complicated acceptance criteria. Ordinarily, an NFA accepts an input string when it has reached any one of a set of accepting final states. That can be extended to boolean combinations of states. Specifically, you construct the automaton for the intersection like you do for the union, but consider the resulting automaton to accept an input string only when it is in (what corresponds to) accepting final states in both automata.

How to find the intersection of two NFA

5 Answers5

Linked