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?

Answer 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!

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

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

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

Answer 5

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.