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.

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:



