Let FA1 be the machine below that accepts all words that end in a:

and let FA2 be the machine below that accepts all words with an odd number of letters (odd length):

Using the algorithm produces the machine below that accepts all words that either have an odd number of letters or that end in a:

The only state that is not a + state is the - state. To get back to the start state, a word must have an even number of letters and end in b.

Let FA1 be:

which accepts all words ending in a, and let FA2 be:

which accepts all words ending in b.

Using the algorithm, we produce:

which accepts all words ending in a or b, that is, all words except Λ. Notice that the state x2 or Y2 cannot be reached since x2 means "we have just read an a" and Y2 means "we have just read a b."

We still have two rules to go.

Rule 3 : If there is an FA1 that accepts the language defined by the regular expression r, and an FA2 that accepts the language defined by the regular expression r2 then there is an FA3 that accepts the language defined by the concatenation r1r2, the product language.

Again, we shall verify this rule by constructive algorithm.

Let L, be the language of all words with b as the second letter. One machine that accepts L, is FA1 below:

Let L2 be the language of all words that have an odd number of a's. One machine for L2 is FA2 on the next page.

Now consider the input string ababbaa. This is a word in the product language L1L2, since it is the concatenation of a word in L1(ab) with a word in L2 (abbaa).

If we begin to run this string on FA1, we would reach the + state after the second letter.

If we could now somehow automatically jump over into FA2, we could begin running what is left of the input, abbaa, starting in the - state.

This remaining input is a word in L2 , so it will finish its path in the + state of FA2.

Basically, this is what we want to build-an FA3 that processes the first part of the input string as if it were FA1; then when it reaches the FA1 + state, it turns into the - state on FA2.

From there it continues processing the string until it reaches the + state on FA2, and we can then accept the input.

Tentatively, let us say FA3 looks something like this:

Unfortunately, this idea, though simple, does not work. We can see this by considering a different input string from the same product language.

The word ababbab is also in L1L2, since abab is in L, (it has b as its second letter) and bab is in L2 (it has an odd number of a's).

If we run the input string ababba first on FA1, we get to the + state after two letters, but we must not say that we are finished yet with the L, part of the input.

If we stopped running on FA1 after ab, we would reach + in FA1, but the remaining input string abbab could not reach + on FA2 since it has an even number of a's.

Remember that FA1 accepts all words with paths that end at a final state. They could pass through that final state many times before ending there. This is the case with the input abab.

It reaches + after two letters. However, we must continue to run the string on FA1 for two more letters. We loop back to + twice.

Then we can jump to FA2 and run the remaining string bab on FA2 . The input bab will start on FA2 in the - state and finish in the + state.

Our problem is this: "How do we know when to jump from FA1 to FA2?"

With the input ababbaa we should jump when we first reach the + in FA1

With the input ababbab (which differs only in the last letter), we have to stay in FA1 until we have looped back to the + state some number of times before jumping to FA2

How can a finite automaton, which must make a mandatory transition on each input letter without looking ahead to see what the rest of the string will be, know when to jump from FA1 to FA2?

So, We have to build a machine that has the characteristic of starting out like FA1 and following along it until it enters a final state at which time an option is reached.

Either we continue along FA1 waiting to reach another + or else we switch over to the start state of FA2 and begin circulating there.

Since the r, part of the input string can generate an arbitrarily long word if it has a star in it, and we cannot be quite sure of when to jump out of FA1 and into FA2

As before, we first illustrate how to build such an FA3 for a specific example. The two machines we shall use are

FA1 = the machine that accepts only strings with a double a in them and

FA2 = the machine that accepts all words that end in the letter b.

We shall start with the state z1 , which is exactly like x1. It is a start state, and it means that the input string is being run on FA1

From z, if we read a b, we must return to the same state x1 , which is z1 again. From z1 if we read an a, we must go to state x2 because we are interested in seeing that the first section of the input string is a word accepted by FA1

Therefore, z2 is the same as x2. From the state z2 if we read a b, we must go back to zl. Therefore, we have the relationships

Z1 = X1

Z2 = X2

The picture of FA3 starts out just like the picture of FA1.

Now if we are in z2 and we read an a, we must go to a new state z3 , which in some ways corresponds to the state x3 in FA1 . However, x3 has a dual identity.

Either it means that we have reached a final state for the first half of the input as a word in the language, for FA1 and it is where we cross over and run the rest of the input string on FA2 , or else it is merely another state that the string must pass through to get eventually to its last state in FA1.

Many strings, some of which are accepted and some of which are rejected, pass through several + states on their way through any given machine.

If we are now in z3 in its capacity as the final state of FA1 for the first part of this input string, we must begin running the rest of the input string as if it were input of FA2 beginning at state y1.

Therefore, the full meaning of being in z3 is:

Notice the similarity between this disjunctive (either/or) definition of z3 and the disjunctive definitions for the z states produced by the algorithm given for the addition of two FA's.

If we are in state z3 and we read an a, we have now three possible interpretations for the state into which this puts us:

= X3 or y, (since being in y, is the same whether we are there for the first time or not) = Z3

Therefore, if we are in z3 and we read an a, we loop back to z3. If we are in state z3 and we read a b, we go to state z4, which has the following meaning:

= x3 or y1 or y2

If an input string ends its path in this state z4 , that means that it could have been broken into two sections, the first going from x, to x3 and the second from y, to y2; therefore, it must be accepted, so z4 is a final state. So far our machine looks like this:

If we are in z4 and we read an a, our choices are:

= x3 or Y1 or Y2 = Z4

Accordingly, if we are in z4 and read a b, we loop back to z4 . The whole machine then looks like this:

Thus we have produced a machine that accepts exactly those strings that have a front section with a double a followed by a back section that ends in b. This we can see because without a double a we never get to z3 and we end in z4 only if the whole word ends in b.

In general, we can describe the algorithm for forming the machine FA3 as follows. First we make a z state for every nonfinal x state in FA1 . For each final state in FA1 we establish a z state that expresses the options that we are continuing on FA1 or are beginning on FA2. From there we establish z states for all situations of the form
are in Xsomething continuing on FA1
or
have just started y1 about to continue on FA2
or
are in Ysomething continuing on FA2

There are clearly only finitely many possibilities for such z states, so FA3 is a finite machine. The transition from one z state to another for each letter of the alphabet is determined uniquely by the transition rules in FA1 and FA2.

So FA3 is a well-defined finite automaton that clearly does what we want, that is, it accepts only strings that first reach a final state on FA1 and then reach a final state on FA2