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.

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}

