This is the final automaton, it has complexity 370 and average step 21.25, both satisfies the restriction.
It use two extra device: one switch "Carry", one integator called "Index".
In the following chapters I will explain how it works.

这是最终版的自动机. 它同时满足复杂度和步数限制, 分别是370复杂度和21.25平均步数.
其包含两个额外的硬件: 一个开关 Carry (进位), 一个累加器叫做 Index (序号).
下面的章节里我会讲解其如何运作.

For simplicity we first consider this automaton. It has avg step 30+, but it can be optimized to obtain the final version.
We compute the addition of two binary numbers from right to left. In this progress, we use Carry to record the addition carry, Index to record which digit we have added (0 for the first digit from right, 1 for the second, etc.).
For each digit, we start from the node Q1. Here we have 4 situations:
(here I say Carry is 0 means it's off, and set it to 0 means turn it off. similar for 1.)

• A1, A2, Carry are all 0. Then we set A3 to 0, Carry to 0.
  
• Exactly one of A1, A2, Carry is 1. Then we set A3 to 1, Carry to 0.
  
• Exactly two of A1, A2, Carry are 1. Then we set A3 to 0, Carry to 1.
  
• A1, A2, Carry are all 1. Then we set A3 to 1, Carry to 1.

However, we dont need really to set A3 to 0 in the first and the third situation,
since it's 0 at the beginning.
Also if Carry doesn't change, we don't need to set it.
E.g. if A1, is 1, A2 is 0, Carry is 1, then we can do nothing, because we need to set A3 to 0 and turn Carry on (which is already on).

So we can reconsider all the 8 situations and find that here is acturally 4 situations:

• If (A1, A2, Carry) = (0,0,0) or (1,0,1) or (0,1,1), do nothing.
  
• If (A1, A2, Carry) = (1,1,1) or (1,0,0) or (0,1,0), set A3 to 1.
  
• If (A1, A2, Carry) = (1,1,0), turn Carry on.
  
• If (A1, A2, Carry) = (0,0,1), set A3 to 1 and turn Carry off.

So we have three nodes Q2, Q3, Q4 and 6 transitions... why not 8? Don't forget we have a "Default" transition.

After we do something we get to the node Q5. Here we increase the counter Index, and move A1/A2/A3 to left. If we get to the final digit, just check carry: if carry is on, set the highest digit of A3 to 1. If not the final digit (Index < 5), return to Q1 and repeat the algorithm.

中文解释先鸽了.

How can we optimize the automaton above? It need 30.10 avg steps.

Notice that we have a useless node Q1. We need pass it 5 times. (In this game, steps count all nodes and transitions you passed. So pass one node acturally gives two steps).
How can we remove it?

Oh, it's simple.
We just copy all transitions from it to the start node and the node Q5 (the copy to Q5 must add the condition "T(Index, {0,1,2,3,4})").
But now it does't work.
This is because we have a "Default" transition from Q1 to Q5.
We want to copy it to a transition from Q5 to Q5 with condition "T(Index, {0,1,2,3,4})",
but it's conflict with all other transitions from Q5 to Q2/Q3/Q4.
If we just make a transition from Q5 to Q5 with "Default", it may cause an infinite loop.
So we create a new node, with a transition with "T(Index, {5}) and T(Carry, {Off})" from Q5 to it,
then just make a transition from Q5 to itself with "Default". Now there is no infinite loop.

Here is another problem: the complexity exceeds the restriction.
We see that at the start node, Carry is must off.
So there is just 4 situation from the start node, and we can use only 3 transitions (by using the default transition).
Now we get the final version of the automaton in the first chapter.