The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
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 by Veteran (98.9k points) | 38 views

1 Answer

0 votes

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 ε. 

answered by (235 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,851 questions
41,835 answers
119,102 comments
41,454 users