Concatenation of 2 finite Automata

Question

I have some problems understanding the algorithm of concatenation of two NFAs.

For example: How to concatenate A1 and A2?

A1:

   #     a      b
   -     -      -
-> s    {s}   {s,p}
   p    {r}    {0}
  *r    {r}    {r}

A2:

   #     a      b
   -     -      -
-> s    {s}    {p}
   p    {s}   {p,r}
  *r    {r}    {s}

Any help would be greatly appreciated.

Answer 1

We connect the accepting states of A1 to the starting point of A2. Assuming that -> means start and * means accepting state.. (I labelled the states according to the original automata, and deleted * from r1 and -> from s2, but added s2 for each possible state change to r1 (once an A1-word would be accepted, we can jump to A2).

   #     a         b
   --    --        --
-> s1    {s1}      {s1,p1}
   p1    {r1,s2}   0
   r1    {r1,s2}   {r1,s2}

   s2    {s2}      {p2}
   p2    {s2}      {p2,r2}
  *r2    {r2}      {s2}

Answer 2

An algorithmic way of doing this is the following:

1. The set of states of the concatenated NFA is just the (disjoint) union of the states of the two automata.
2. The initial state of the new NFA is the initial state of the first NFA.
3. The accepting states of the new NFA are the accepting states of the second NFA.
4. Every transition from either original NFA is a transition in the new NFA.
5. The only new transitions are $\varepsilon$-moves from each accepting state of the first NFA to the initial state of the second NFA.

---

As a pictorial example (not using the NFAs from the OP), consider the following two NFAs:

Concatenating them in the fashion above would yield the following NFA: