0

So i have this problem where I have to find the intersection of two NFA and I don't find any solution. So you have two automatons m1 and m2 with m1=(Q1, Σ1, Δ1, q1, F1) and m2=(Q2, Σ2, Δ2, q2, F2).

I think that Q is formed by a combination of states of Q1 and Q2, so that any state of m is made of every possible combination of states of m1 and m2.

Then Σ is formed by the union of Σ1 and Σ2 I suppose.

Then the begin end end state is made of the combination of begin and end state of m1 and m2.

Buth my question is: how are F and Δ formed. Is it just the cartesian product or is it something special?

Does anyone know if there is a difference or am i totally wrong with the other parts?

So i had this excercise and found the following solution. So the excercise is to make an intersection of these two NFA's: Excercise

This is my reduced solution: Final solution

Can anyone let me know if i'm right?

Bram Kelchtermans
  • 9
  • 1
  • 4
  • 1
    Possible duplicate of [How to find the intersection of two NFA](http://stackoverflow.com/questions/21662041/how-to-find-the-intersection-of-two-nfa) – harold Nov 26 '15 at 18:14

1 Answers1

0

F is formed by the union of F1 and F2 as we have the "or" condition and again any given string of F1 should be accept in F so we have F as union of set of final states in F1 and F2 and i suppose this would be minimizable depending on the set of alphabets, the transitions depend on the transition of both F1 and F2 and should be converted to other form as F1 cannot transit for any input of F2 so again no. of transitions is cartesian product of F1 and F2.

Sharat Ainapur
  • 19
  • 8