DFA for $a+b=c$, where $a,b,c$ are input in parallel

Question

I've faced this question in my homework, it's a bonus question so it's harder than I could do now with my current knowledge, so if anyone could help I'll be thankful.

We're given $\Sigma=\{0,1\}^3$. We think of the 'letters' of the language as column vectors, so every $w\in\Sigma ^*$ is a matrix $M_w$ that consists of $3$ rows and $n$ columns. We refer to the binary numbers represented by $M_w$ rows by $a_w,b_w,c_w$. For example: if $w=(0,1,1)(1,0,1)$ so: $$ M_w = \begin{array}{ccccc} 0&1&&a_w&=01 \\ 1&0&\Longrightarrow&b_w&=10 \\ 1&1&&c_w&=11 \end{array} $$

We define the language $L=\{w\in \Sigma ^* \mid a_w+b_w=c_w\}$. For example, the $w$ above is related to $L$. However, $w'=(0,1,1)(1,0,1)(1,0,0)$ is not since $a_w=011, b_w=100, c_w=110$.

Question: Describe DFA (Deterministic Finite Automata) that accepts $L$.

Answer 1

Define function $d:\Sigma^*\to \mathbb Z$, $d(w)=a_w+b_w-c_w$. So $w\in L\iff d(w)=0$.

Let us see how $d(w)$ changes if $w$ is extended by a letter $\sigma=\begin{pmatrix}a\\b\\c\end{pmatrix}\in\Sigma$.

Let $w'=w\sigma$. By the definition of a binary number, we have \begin{aligned} a_{w'} &= 2\times a_{w} + a\\ b_{w'} &= 2\times b_{w} + b\\ c_{w'} &= 2\times c_{w} + c\\ \end{aligned} So, $$d(w') = 2\times d(w) + d(\sigma)$$ Note that $-1\le d(\sigma)\le 2$.

• $d(w)\le -2 \implies d(w')\le -2$
• $d(w)=-1 \implies d(w')=-2 + d(\sigma)$
• $d(w)=0 \implies d(w')=d(\sigma)$
• $d(w)\ge 1 \implies d(w')\ge 1$

Let us construct a DFA with three states $q_{\le-2\,\text{or}\,\ge1}$, $q_{=-1}$, and $q_{=0}$.

• $q_{\le-2\,\text{or}\,\ge1}$ for $w$ such that $d(w)\le-2$ or $d(w)\ge1$.
• $q_{=-1}$ for $w$ such that $d(w)=-1$.
• $q_{=0}$ for $w$ such that $d(w)=0$.

Readers can specify the accept state and the transition function so that the DFA accepts $L$.

---

Here is a nice DFA provided by OP.