Answer

Language: $L = \{ w \in \{0,1\}^* \mid \text{value}_2(w) \equiv 0 \pmod 4 \}$

Interpret string as binary number (most significant bit first), check divisibility by 4.

---

Key Observation

A binary number is divisible by 4 iff its last two bits are 00 (or the string is just "0" or empty, treated as 0).

• Binary $x \equiv 0 \pmod 4 \iff x$ ends in 00.
• Special case: empty string $\epsilon$ and "0" represent 0, divisible by 4.

---

DFA Construction (4 states)

Track value modulo 4. States = residues $\{0,1,2,3\}$.

DFA: $M = (Q, \Sigma, \delta, q_0, F)$

• $Q = \{q_0, q_1, q_2, q_3\}$ where $q_r$ = value $\equiv r \pmod 4$
• $\Sigma = \{0,1\}$
• $q_0$ = start (value 0)
• $F = \{q_0\}$ (residue 0)

Transition: On input bit $b \in \{0,1\}$:

Transition Table:

State \ Input	0	1
$q_0$ (0)	$q_0$	$q_1$
$q_1$ (1)	$q_2$	$q_3$
$q_2$ (2)	$q_0$	$q_1$
$q_3$ (3)	$q_2$	$q_3$

Derivation:

• $2 \times 0 + 0 = 0 \to q_0$
• $2 \times 0 + 1 = 1 \to q_1$
• $2 \times 1 + 0 = 2 \to q_2$
• $2 \times 1 + 1 = 3 \to q_3$
• $2 \times 2 + 0 = 4 \equiv 0 \to q_0$
• $2 \times 2 + 1 = 5 \equiv 1 \to q_1$
• $2 \times 3 + 0 = 6 \equiv 2 \to q_2$
• $2 \times 3 + 1 = 7 \equiv 3 \to q_3$

---

State Diagram

---

Simplified 3-State DFA (Using Last-Two-Bits Insight)

Since divisibility by 4 depends only on last 2 bits = 00:

DFA with 3 states:

• $q_0$: start, also accept (0 or empty or ...00)
• $q_1$: last bit = 1
• $q_2$: last bit = 0, previous ≠ 0 (i.e., ends in 10)

State \ Input	0	1
$q_0$ (accept)	$q_0$	$q_1$
$q_1$	$q_2$	$q_1$
$q_2$	$q_0$	$q_1$

$F = \{q_0\}$. $q_0$ = last two bits 00 (or empty/"0").

Why 3 states minimal: Myhill-Nerode: $\epsilon, 1, 10$ are pairwise distinguishable mod 4.

---

Test Cases

Input	Value	Path	Accept?
$\epsilon$	0	$q_0$	Yes
0	0	$q_0 \xrightarrow{0} q_0$	Yes
100	4	$q_0 \to q_1 \xrightarrow{0} q_2 \xrightarrow{0} q_0$	Yes
1000	8	$q_0 \to q_1 \to q_2 \to q_0 \to q_0$	Yes
10	2	$q_0 \to q_1 \xrightarrow{0} q_2$	No ($q_2
otin F$)
101	5	$q_0 \to q_1 \xrightarrow{0} q_2 \xrightarrow{1} q_1$	No
1100	12	ends in $q_0$	Yes

---

Regular Expression

$(0+1)^*00 + 0$

(All strings ending in 00 plus the single 0; $\epsilon$ can be included as (0+1)*00 | 0 | \epsilon)

---

Final Answer

DFA with 4 states (mod 4 tracking) or minimal 3 states:

• States: residues 0,1,2,3 (or 3-state: 00, ends-in-1, ends-in-10)
• Transitions: $\delta(q_r, b) = q_{(2r+b)\bmod 4}$
• Accept: $q_0$ only
• Binary divisible by 4 ⇔ ends in 00 (or is 0/ε)

DFA(3 states):
q0 --0--> q0
q0 --1--> q1
q1 --0--> q2
q1 --1--> q1
q2 --0--> q0
q2 --1--> q1
Accept: q0