How can I show that the set of decimal representations of the natural numbers divisible by4 is regular?

Question

How can I show that the set of decimal representations of the natural numbers divisible by four is regular? I'm stack on this problem. I tried some solutions but I know It is incorrect. Please help me. If you use more details in your explanation, would be better.

Thank you"

I added a larger image of what I tried so far the image

Let $L$ be the language of natural numbers divisible by $4$. We want a DFA $M(L)=\{Z,\Sigma,\delta,z_A,E\}$ with $Z=\{z_A,z_S,z_R,z_0,z_1,z_2,z_3\}$ and $\Sigma=\{0,1,2,3,4,5,6,7,8,9\}$ that recognizes $L$. $E=\{z_S,z_0\}$.

$$\begin{array}{c|cc} \delta&z_A&z_S&z_R&z_0&z_1&z_2&z_3\\\hline r_0=0&z_S&z_R&z_R&z_0&z_2&z_0&z_2\\ r_0=8,4&z_0&z_R&z_R&z_0&z_2&z_0&z_2\\ r_1=9,5,1&z_1&z_R&z_R&z_1&z_3&z_1&z_3\\ r_2=6,2&z_2&z_R&z_R&z_2&z_0&z_2&z_1\\ r_3=7,3&z_3&z_R&z_R&z_3&z_1&z_3&z_1 \end{array}$$

$\delta:Z\times\Sigma:\langle z_i,r_k\rangle\mapsto z_j$ with $i\in\{0,1,2,3\}$ and $2i+k\equiv j\pmod 4$, $k,j\in\{0,1,2,3\}$, except that all words beginning with $0$ are thrown away ($z_R$) by the machine except the word $0$ itself, which is accepted by its own state $z_S$.

We want to prove that each word $w$ over the alphabet $\Sigma$ that does not begin with $0$ takes the automaton $M$ to $z_i$ when $w\equiv i\pmod 4$. We prove this by induction on the length $n$ of $w$.

When $n=1$ we have $$\begin{align*}&w=8,4\equiv 0\pmod4\implies z_0\\&w=1,5,9\equiv1\pmod4\implies z_1\\&w=2,6\equiv2\pmod4\implies z_2\\&w=3,7\equiv3\pmod4\implies z_3\end{align*}$$

Our induction hypothesis is that the result holds for words of length $n$.

Answer 1

A natural number whose decimal representation is $d_nd_{n-1}\ldots d_1d_0$ is divisible by $4$ if and only if the numbers whose decimal representation is $d_1d_0$ is divisible by $4$, since

$$d_nd_{n-1}\ldots d_200=100\cdot d_n\ldots d_2=4(25\cdot d_n\ldots d_2)\,.$$

It’s not hard to show that $d_1d_0$ is divisible by $4$ if and only if

• $d_1$ is even and $d_0\in\{0,4,8\}$, or
• $d_1$ is odd and $d_0\in\{2,6\}$.

You can do it with a DFA $M$ that has an initial state $z_e$ ($e$ for even) and just two other states, $z_{ea}$ ($ea$ for even acceptor) and $z_o$ ($o$ for odd). See if you can complete the transition table: it will have just three types of input. If you get stuck, leave a question for me.