Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to find the intersection of two NFA

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?

like image 246
Aditya Nambiar Avatar asked Feb 09 '14 16:02

Aditya Nambiar


1 Answers

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!

like image 165
templatetypedef Avatar answered Nov 15 '22 05:11

templatetypedef