CMI2016-B-5

Question

For a string $x=a_0a_1 \ldots 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.

Answer 1

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(a₀a₁a₂...a_i) = n, then 

If a_i+1 = 0, val(a₀a₁a₂...a_i) = n*3 + 0

If a_i+1 = 1, val(a₀a₁a₂...a_i) = n*3 + 1

If a_i+1 = 2, val(a₀a₁a₂...a_i) = 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 ε. 

Answer 2

There is an algorithm for construction of such DFA

To construct in mod x DFA in base b

number of rows = x

number of columns = b

number of entries = x*b

number of states in DFA = x

so for our example x=4 base b=3 

state ={q0,q1,q2,q3}  q0 = remainder 0 , q1= remainder 1 and so on 

Now we will construct transition table for such DFA

fill out entries q0,q1,q2 in circular order till the end of the column and start with next state in next row first column 

State \input	0	1	2
q0	q0	q1	q2
q1	q3	q0	q1
q2	q2	q3	q0
q4	q1	q2	q3

one can see pattern q0,q1,q2,q3 is repeated in transition diagram 

number of rows = 4 number of column =3 and entires = 12

Answer 3