Answer

Language: $L = \{ w \in \{0,1,2\}^* \mid \text{no } 00, 11, 22 \text{ as substring} \}$

DFA Construction

Idea: Track the last symbol seen (0, 1, or 2) or "none yet" (start). Forbid transition on same symbol as last.

States:

• $q_\epsilon$ : start, no symbol yet (also accepting)
• $q_0$ : last symbol was 0 (accepting)
• $q_1$ : last symbol was 1 (accepting)
• $q_2$ : last symbol was 2 (accepting)
• $q_\times$ : dead/reject state (non-accepting)

Alphabet: $\Sigma = \{0,1,2\}$

Transition Function $\delta$:

State $\backslash$ Input	0	1	2
$q_\epsilon$	$q_0$	$q_1$	$q_2$
$q_0$	$q_\times$	$q_1$	$q_2$
$q_1$	$q_0$	$q_\times$	$q_2$
$q_2$	$q_0$	$q_1$	$q_\times$
$q_\times$	$q_\times$	$q_\times$	$q_\times$

Formal DFA: $M = (Q, \Sigma, \delta, q_\epsilon, F)$ where

• $Q = \{q_\epsilon, q_0, q_1, q_2, q_\times\}$
• $\Sigma = \{0,1,2\}$
• $q_\epsilon$ initial
• $F = \{q_\epsilon, q_0, q_1, q_2\}$ (all except dead)
• $\delta$ as table above

State Diagram (Mermaid)

Regular Expression (for verification)

$L = \epsilon + (0+1+2)( (0+1+2) - (00+11+22) )^*$
More compactly using complement:
$L = \Sigma^* \setminus \Sigma^*(00+11+22)\Sigma^*$

Test Cases

Input	Path	Accept?
$\epsilon$	$q_\epsilon$	Yes
$012$	$q_\epsilon \xrightarrow{0} q_0 \xrightarrow{1} q_1 \xrightarrow{2} q_2$	Yes
$010$	$q_0 \to q_1 \to q_0$	Yes
$00$	$q_0 \xrightarrow{0} q_\times$	No
$101$	$q_1 \to q_0 \to q_1$	Yes
$2121$	$q_2 \to q_1 \to q_2 \to q_1$	Yes

Minimality

5 states are minimal (Myhill-Nerode: $\epsilon, 0, 1, 2$ are pairwise distinguishable; dead state needed).

Final Answer

DFA with 5 states ($q_\epsilon, q_0, q_1, q_2, q_\times$), accepting all except $q_\times$, transitions as table above. Rejects any string with $00, 11,$ or $22$.