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][101] = 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.

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

1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.