38 views
For a string $x=a_0a_1 \ cdots a_{n-1}$ over the alphabet $\{0, 1, 2\}$, define $val(x)$ to be the value of $x$ interpreted as a ternary number, where $a_0$ is the most significant digit. More formally, $val(x)$ is given by $$\Sigma_{0 \leq i < n} 3^{n-1-i} \cdot a_i.$$

Design a finite automaton that accepts exactly the set of strings $x \in \{0, 1, 2\}^*$ such that $val(x)$ is divisible by 4.
asked in Others | 38 views

We are talking about base 3 numbers in class modulo 4.

val(x) denotes the value of x in decimal, where the string is given in the format from MSB to LSB.

Let us say after processing i digits, val(a0a1a2...ai) = n, then

If ai+1 = 0, val(a0a1a2...ai) = n*3 + 0

If ai+1 = 1, val(a0a1a2...ai) = n*3 + 1

If ai+1 = 2, val(a0a1a2...ai) = n*3 + 2

Since we are only interested in mod 4 of these numbers, let us say n is either of 4*n, 4*n+1, 4*n + 2, 4*n + 3 (i.e. n leaves a remainder of 0, 1, 2, 3 on mod 4 respectively). We will construct the transition function as below:

 0 1 2 4*n          (S0) ((4*n)*3)%4 = 0 (S0) ((4*n)*3+1)%4 = 1 (S1) ((4*n)*3+2)%4 = 2 (S2) 4*n + 1   (S1) ((4*n+1)*3)%4 = 3 (S3) ((4*n+1)*3+1)%4 = 0 (S0) ((4*n+1)*3+2)%4 = 1 (S1) 4*n + 2   (S2) ((4*n+2)*3)%4 = 2 (S2) ((4*n+2)*3+1)%4 = 3 (S3) ((4*n+2)*3+2)%4 = 0 (S0) 4*n + 3   (S3) ((4*n+3)*3)%4 = 1 (S1) ((4*n+3)*3+1)%4 = 2 (S2) ((4*n+3)*3+2)%4 = 3 (S3)

From this we can easily construct a DFA, with 4 states, with initial and final states as S0. We can even add a new start state because this DFA will even accept ε.