Ternary representation of an integer that is a multiple of 5

Consider the problem of building a Deterministic Finite Automaton (DFA) over $\{0, 1, 2\}$ to accept ternary numbers that are multiples of 5. For the sake of simplicity, assume that the empty string, $\epsilon$ , should be accepted.

States

The resulting DFA will have $5$ states. Each state will keep track of one of five possible remainders – $0, 1, 2, 3, 4$ .

For example, the state $r_3$ , keeps track of the information that the ternary string read upto this point, when divided by $5$ , leaves remainder $3$ .

Tracking remainder

Consider the ternary string $122$ . The decimal equivalent of this ternary number is $17$ . $17$ when divided by $5$ , leaves remainder $2$ . Thus, if the above DFA already read the input $122$ , it will currently be in state $r_2$ .

Symbol $0$

If the string $122$ is followed by a $0$ , the ternary number $1220$ is equivalent to $51$ in decimal. In effect, seeing a single $0$ at the end of a ternary string, multiplies the integer equivalent by $3$ . The same logic applies to the remainder. $51$ when divided by $5$ , leaves remainder $1$ , which is the same as $(2 * 3) mod 5 \equiv 1$ .

Old Ternary	Old Decimal	$mod 5$	Symbol	New Ternary	New Decimal	$mod 5$
$122$	$17$	$2$	$0$	$1220$	$17 * 3 = 51$	$(2*3) mod 5 \equiv 1$

Symbol $1$

If the string $122$ is followed by a $1$ , the ternary number $1221$ is equivalent to $52$ in decimal. In effect, seeing a single $1$ at the end of a ternary string, multiplies the integer equivalent by $3$ and then adds a $1$ . The same logic applies to the remainder. $52$ when divided by $5$ , leaves remainder $2$ , which is the same as $(2 * 3 + 1) mod 5 \equiv 2$ .

Old Ternary	Old Decimal	$mod 5$	Symbol	New Ternary	New Decimal	$mod 5$
$122$	$17$	$2$	$1$	$1221$	$17 * 3 + 1 = 52$	$(2*3 + 1) mod 5 \equiv 2$

Symbol $2$

If the string $122$ is followed by a $2$ , the ternary number $1222$ is equivalent to $53$ in decimal. In effect, seeing a single $2$ at the end of a ternary string, multiplies the integer equivalent by $3$ and then adds a $2$ . The same logic applies to the remainder. $53$ when divided by $5$ , leaves remainder $3$ , which is the same as $(2 * 3 + 2) mod 5 \equiv 3$ .

Old Ternary	Old Decimal	$mod 5$	Symbol	New Ternary	New Decimal	$mod 5$
$122$	$17$	$2$	$2$	$1222$	$17 * 3 + 2 = 53$	$(2*3 + 2) mod 5 \equiv 3$

General Formula

Consider any ternary string $w$ , that leaves remainder $r$ when divided by $5$ . Upon seeing a new symbol after $w$ , the remainder changes as follows

Ternary String	Remainder	New Symbol	New Remainder
$w$	$r$	$0$	$(3r) mod 5$
$w$	$r$	$1$	$(3r + 1) mod 5$
$w$	$r$	$2$	$(3r + 2) mod 5$

$r$ can take values from $0$ to $4$ . Substituting these values in the above table, generates the following

Remainder	New Symbol	New Remainder
$0$	$0$	$(3 * 0) mod 5 \equiv 0$
$0$	$1$	$(3 * 0 + 1) mod 5 \equiv 1$
$0$	$2$	$(3 * 0 + 2) mod 5 \equiv 2$
$1$	$0$	$(3 * 1) mod 5 \equiv 3$
$1$	$1$	$(3 * 1 + 1) mod 5 \equiv 4$
$1$	$2$	$(3 * 1 + 2) mod 5 \equiv 0$
$2$	$0$	$(3 * 2) mod 5 \equiv 1$
$2$	$1$	$(3 * 2 + 1) mod 5 \equiv 2$
$2$	$2$	$(3 * 2 + 2) mod 5 \equiv 3$
$3$	$0$	$(3 * 3) mod 5 \equiv 4$
$3$	$1$	$(3 * 3 + 1) mod 5 \equiv 0$
$3$	$2$	$(3 * 3 + 2) mod 5 \equiv 1$
$4$	$0$	$(3 * 4) mod 5 \equiv 2$
$4$	$1$	$(3 * 4 + 1) mod 5 \equiv 3$
$4$	$2$	$(3 * 4 + 2) mod 5 \equiv 4$

Transitions

In the above table, the first column maps to one of the states of the DFA. The second column, maps to a transition symbol. The third column maps to the state the transition points to. Converting the table to states and transitions results in

From State	Symbol	To State
$r_0$	$0$	$r_0$
$r_0$	$1$	$r_1$
$r_0$	$2$	$r_2$
$r_1$	$0$	$r_3$
$r_1$	$1$	$r_4$
$r_1$	$2$	$r_0$
$r_2$	$0$	$r_1$
$r_2$	$1$	$r_2$
$r_2$	$2$	$r_3$
$r_3$	$0$	$r_ 4$
$r_3$	$1$	$r_0$
$r_3$	$2$	$r_1$
$r_4$	$0$	$r_2$
$r_4$	$1$	$r_3$
$r_4$	$2$	$r_4$