Combining two DFAs into an NFA to recognize concatenation

Question

Suppose we have two separate DFAs that each recognize their own language. What is the most efficient way to combine these two DFAs into one NFA that recognizes the concatenation of both languages?

Answer 1

To make an NFA for the concatenation of $A$ and $B$, put the states of $A$ and $B$ together.

Keep all the transitions of $A$ and of $B$, and add $\epsilon$-transitions from the final states of $A$ to the initial state of $B$.

Make the initial state of the combined machine the same as the initial state of $A$.

Make the final states of the combined machine the same as the final states of $B$.

This construction probably appears in your book, as part of the proof that regular expressions are equivalent to NFAs. The proof must include a method for converting a regular expression of the form $AB$ to an NFA, given NFAs for regular expressions $A$ and $B$. It certainly appears in the Hopcroft and Ullman book.

Answer 2

Given DFAs $M'$ and $M''$ which recognise languages $L'$ and $L''$, consider the NFA $M$ defined as follows.

The states of $M$ are the union of those of $M'$ and $M''$; the initial state of $M'$ is an initial state of $M$, and if the empty word is accepted by $M'$ then the initial state of $M''$ is a second initial state of $M$. The final states of $M$ are just those of $M''$. We retain all the transitions in $M'$ and $M''$, and in addition, for any arrow leading to an accepting state in $M'$ we add a duplicate arrow leading to the initial state of $M''$.

I'll leave you to convince yourself that this works.

As to "most efficient", no real idea, but as we have taken only the states we had in the two given DFAs, it's pretty hard to imagine getting anything smaller in general.