How to find the intersection of two NFA

Aditya Nambiar picture Aditya Nambiar · Feb 9, 2014 · Viewed 13.8k times · Source

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

templatetypedef picture templatetypedef · Feb 9, 2014

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 (qi, rj) in the cross-product automaton, you add an ε-transition from that state to each pair of states (qk, rj) where there's an ε-transition in the first machine from qi to qk and to each pair of states (qi, rk) where there's an ε-transition in the second machine from rj to rk.

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

Hope this helps!