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!