# How to design a DFA that accepts the language of pairs of binary words (a,b) with 5a=b?

Let $$\begin{bmatrix}0\\ 0\end{bmatrix}$$ be a two-column vector with $$0$$ in the first row and $$0$$ in the second row.
Let $$\Sigma_2 = \left\{ \begin{bmatrix}0\\ 0\end{bmatrix}, \begin{bmatrix}0\\ 1\end{bmatrix}, \begin{bmatrix}1\\ 0\end{bmatrix}, \begin{bmatrix}1\\ 1\end{bmatrix}\right\}$$ be the set of all 2-element column vectors of binary digits.

$$A =\{\begin{bmatrix}u\\ v\end{bmatrix}\in {\Sigma_2}^*\mid [v]_2 = 5[u]_2\}$$

Where $$[x]_k$$ is the $$x$$ to the base $$k$$. So $$[x]_2$$ is a binary number. $$A$$ is the language of words where the second row is five times the first row. For example, $$\begin{bmatrix}0\\1\end{bmatrix}\begin{bmatrix}0\\ 0\end{bmatrix}\begin{bmatrix}1\\1\end{bmatrix}$$ i.e. $$1$$ and $$5$$.

What I've realized so far is that the second row must be the first row shifted twice eg. $$001 \to 100$$ plus the first row. For example. $$ = 001$$ {shift2} $$100 + 001$$. What I've been trying to do as of late is to design a DFA to recognize a language where the second row is the first row shifted twice and move on from there.

I've been at this for over a day now. Please provide some insight if you can.

• Yes, I know pumping Lemma. I have been taught up to Context-Free Languages Feb 12 at 19:35
• I am sorry I wasn't taught that thoroughly yet. I'll do some research and get back to you Feb 12 at 22:07
• Could you give some guidance? @JohnL.? Feb 12 at 22:13

Define function $$d:{\Sigma_2}^*\to \mathbb Z$$, $$d(w)=\underline w-5\overline w$$, where

• $$\overline w$$ is the base-$$2$$ number formed by the digits on the first row of the letters in $$w$$
• $$\underline w$$ is the base-$$2$$ number formed by the digits on the second row of the letters in $$w$$.

For example, if $$w=\begin{bmatrix}0\\1\end{bmatrix}\begin{bmatrix}0\\1\end{bmatrix}\begin{bmatrix}1\\0\end{bmatrix}$$, then $$\overline w=(001)_2=1$$, $$\underline w=(110)_2=6$$, $$d(w)=6-5\cdot1=1$$.

The language in the question $$A$$ is $$\{w\in{\Sigma_2}^*\mid d(w)=0\}$$

How does $$d(w)$$ change if $$w$$ is extended by a letter $$\sigma=\begin{bmatrix}a\\b\end{bmatrix}\in\Sigma_2$$?

Let us check. Let $$w'=w\sigma$$. By the definition of a base-$$2$$ number, we have \begin{aligned} \overline{w'} &= 2\times \overline{w} + a\\ \underline{w'} &= 2\times \underline{w} + b\\ \end{aligned} So, $$d(w') = 2\times d(w) + d(\sigma)$$ Since $$-5\le d(\sigma)\le 1$$, we know

• $$d(w)\le -1 \implies d(w')\le -1$$
• $$d(w)\ge 5 \implies d(w')\ge 5$$

Let us construct a DFA with 7 states $$q_{\le-1}, q_0, q_1, q_2, q_3, q_4, q_{\ge5}$$, where

• $$q_{\le-1}$$ for words $$w$$ such that $$d(w)\le-1$$.
• $$q_{i}$$ for words $$w$$ such that $$d(w)=i$$, where $$0\le i\le 4$$.
• $$q_{\ge5}$$ for words $$w$$ such that $$d(w)=5$$.

The transitions $$\delta$$ is defined by

• $$\delta(q_{\le-1}, \cdot)=q_{\le-1}$$.
• $$\delta(q_{i}, \sigma)=q_{2*i+d(\sigma)}$$, for $$0\le i\le 4$$. Here $$q_{2*i+d(\sigma)}$$ should be understood as
• $$q_{\le-1}$$ if $$2*i+d(\sigma)\le -1$$.
• $$q_{\ge5}$$ if $$2*i+d(\sigma)\ge 5$$.
• $$\delta(q_{\ge5}, \cdot)=q_{\ge5}$$.

$$q_0$$ is the start state and the unique accept state.

By the construction above, it is straightforward to check that the DFA accepts $$A$$.