What is the DFA for this language? Consider the $n$-bit binary representation of a natural number. Consider the language 
\begin{multline}
L= \{a_0b_0c_0 \dotsm a_{n-1} b_{n-1} c_{n-1} \mid n \in \mathbb{N} \text{ and for $0 \leqslant i< n$}, a_i, b_i, c_i \in \{0,1\}\\ 
 \text{ and } (a_{n-1} \dotsm a_0)+ (b_{n-1} \dotsm b_0) = (c_{n-1} \dotsm c_0)_2\}
\end{multline}
For example, since $4 + 1 = 5$, $4 = (000100)_2$, $1 = (000001)_2$ and $5 = (000101)_2$, then $011 000 101 000 000 000 \in L$.
I created a DFA that accepts all the correct additions, but it also accepts $1+2=4$, which should be wrong. Moreover, I used this example as my starting point, but I don't know how to create a DFA from this FSM.   
 A: Since the DFA reads one bit at a time, and it reads both the operands and their claimed sum, you need 10 states.  One of them is both initial and final, and one is a trap state.
Before it reads the $a_k$ bit, the DFA may be in one of two states, depending on the carry from the previous $k$ bits.  (For $k=0$, the DFA is in the $0$-carry state, which is initial.)
Between reading $a_k$ and $b_k$, the DFA may be in one of three states, depending on the total number of ones between the carry-in and $a_k$.  Likewise, between reading $b_k$ and $c_k$, the DFA may be in one of four states, depending on the total number of ones among the carry-in, $a_k$, and $b_k$.  These states encode the four combinations of output bit and carry-out.
From the four states reached after reading $b_k$, the DFA reads $c_k$.  If it has the right value, it goes to one of the two states in the first layer, depending on the carry-out.  Otherwise it moves to the trap state and stays there forever.
Since no two states are equivalent in this DFS, it is minimal.
