3.3.6 Union

Continuation.

To obtain a method for constructing union-automata, we have to translate some of the ideas underlying our proof of the equivalence between regular expressions and FSAs in Section 3.1.5. We proceed again by giving further clauses of start/2, trans/4 and final/2.

Remember that we gave the automaton for the union of two regular languages a brand new start state. This is encoded in the clause we add to start/2:

start((_;_),start).

Assume that we are building a union-automaton from a1 and a2. The first setof/3-call will then search for transitions out of the new start state as follows:

setof(D,X^trans(cp((a1;a2),b1),start,X,D),Ds)

This leads to a call:

trans((a1;a2),start,X,D)

As we've seen in Section 3.1.5, our union-automaton should contain jump arcs from the new start state to (copies of) the start states of a1 and a2. We add the following clauses to trans/4 for this purpose:

trans((A1;_),start,1/S1,'#'):-
  start(A1,S1).

trans((_;A2),start,2/S2,'#'):-
  start(A2,S2).

When we were building a union-automaton from two automata and in Section 3.1.5, we assumed that the states in both automata were disjoint. To the same effect we will generally give states that come from a prefix 1/ and states that come from a prefix 2/ in our implementation of the union-operation. So even if and have some state names in common, the corresponding states in our union automaton will have different names.

The interior of our union automaton is build up by taking over all transitions from the automata to be united and prefixing their start and end states by 1/ or 2/:

trans((A1;_),1/S1,1/D1,X):-
  trans(A1,S1,D1,X).

trans((_;A2),2/S2,2/D2,X):-
  trans(A2,S2,D2,X).

For the final states, we deviate a little from the method discussed in Section 3.1.5. There we introduced one new final state and added jump arcs into it from all former final states. But we don't have to insist on having only one final state in our union-automaton. So we can simply prefix and take over the final states from the two input automata. Hence we just add the following two clauses to final/2:

final((A1;_),1/S1):-
  final(A1,S1).

final((_;A2),2/S2):-
  final(A2,S2).