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?

Solution 1

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!

Solution 2

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.

Solution 3

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.

Solution 4

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:

1. m1 accepting the language {w | w contains '11' as a substring}
2. 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.

View more solutions

Comments

[Aditya Nambiar]

so there is no easy method like just adding epsilon as in the union case?

[templatetypedef]

@AdityaNambiar- Not to the best of my knowledge.

[Stefan]

Hmm... how do you take the negation of an NFA, other than by turning it into a DFA first?

[harold]

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?

[templatetypedef]

@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.

[pallly]

@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.

[Christoph Burschka]

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.)

[MattS]

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.

[xFioraMstr18]

[Never mind, I retract my comment.]

[xFioraMstr18]

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").