0

I have been trying to formalise the union of two finite state automata without making use of epsilon transitions. I want to create a new initial start state for the new automata and from this new start state create transitions to the reachable states from the start state of the separate automata by copying these transitions.

Given an FSA 

M1 = <Σ1, Q_1, q0_1, ->_1>

where Σ1 = alphabet, Q_1 is the set of states, q0_1 is the start state, and ->_1 is the transitions of M1.

Given another FSA 

 M2 = <Σ2, Q_2, q0_2, ->_2>

where Σ2 is the alphabet, Q_2 is the set of states, q0_2 is the start state, and ->_2 is the transitions of M2.

Now I have defined the FSA M+ = M1 ∪ M2 as the FSA :

 M_+ = <Σ+, Q_+, q0_+, ->_+>
 Σ+ = Σ1 ∪ Σ2 - alphabet of both
 Q_+ = Q_1 ∪ Q_2 ∪ {q0_+},
 q0+ is the new initial start state 
 ->_+ = ->_1 ∪ ->_2 ∪ ->_C

I have been finding trouble defining ->_C - the new transitions to the reachable states of M1 and M2. I defined the type of ->_C to be as follows: Q x 2^Σ x 2^Q. It is required to be a set however I am not sure how to define it formally. Any help will be very much appreciated.

enter image description here

Andre Croucher
  • 395
  • 1
  • 3
  • 9
  • Do you want a machine M+ such that L(M+) = L(M1) U L(M2), or something else? Does http://stackoverflow.com/a/7798776/847269 answer your question? – Patrick87 May 05 '17 at 13:23
  • Hi, thanks for the reply. I would just like to know how to define the transitions from the new start state to the states of M1 and M2 by copying their transitions from the previous start states (q0_1 and q0_2) – Andre Croucher May 06 '17 at 13:45

1 Answers1

1

Why Q x 2^Σ x 2^Q ? Better Q x Σ x 2^Q; transitions are defined separately for every possible letter. Otherwise you do not know which state belongs to which letter(s).

->C := { (q0+,x,P) : (q0_1,x,P) \in ->_1 OR (q0_2,x,P) \in ->_2 }

Peter Leupold
  • 1,162
  • 1
  • 9
  • 16
  • Hi, thanks for the reply, I would like to have a definition to suit the transitions for the automaton in the image attached above. My attempt was the following : --->C = {(q0_+, A, q1) | (q0_1,A,q2) \in ->_1 AND (q0_1,B,q2) \in ->_2}.....however my problem is that this does not handle both A and B but rather only A. – Andre Croucher May 15 '17 at 09:01
  • Be careful with what is a variable and what is a letter. In your diagram, A and B are letters. In my the definition of ->_C, x is a variable and thus handles all letters. Your version here in the comment is a bit unclear. There cannot be any transitions from q0_1 to q_2 in ->_2, because the states are from the first automaton. If you want to use letters instead of variables, you really have to define the set for every letter seperately and take the union. – Peter Leupold May 15 '17 at 11:44