Finite Automata $(FA)$ or Finite State Machine to add two integers can be constructed using two states:
- $q_0$: Start state to represent carry bit is $0$
- $q_1$: State to represent carry bit is $1$
The inputs to $FA$ will be pair of bits i.e. $00, 01, 10,$ and $11$
The FA starts in-state $1$ (since carry is $0$) and inputs a pair of bits. If the pair is $11$, the FA outputs a $0$ and switches to state $2$ (since the carry is $1$), where the next pair of bits is input and is added to a carry bit of $1$.
Example: Consider the addition of $52$ and $21$
- $110100$ - (binary representation of $52$)
- $010101$ - (binary representation of $21$)
Since adding numbers is done from right to left, the first input symbol is $01$, representing a $0$ in the rightmost (binary) digit of $52$ and a $1$ in the rightmost digit of $21$. The machine enters state $q_0$ (since there is no carry) and outputs a $1$. The next input is $00$ because both numbers have zero as the second rightmost digit. The machine enters state $q_0$ and outputs $0$. The next input is $11$. The machine enters state $q_1$ (since the carry is $1$) and outputs $0$. Being in-state $q_1$ means that there is a carry from this position into the next. And the remaining bits can be worked out to get $1001001 ($i.e. $73).$