Concatenation of 2 finite Automata 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.
 A: 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}

A: An algorithmic way of doing this is the following:


*

*The set of states of the concatenated NFA is just the (disjoint) union of the states of the two automata.

*The initial state of the new NFA is the initial state of the first NFA.

*The accepting states of the new NFA are the accepting states of the second NFA.

*Every transition from either original NFA is a transition in the new NFA.

*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:



