The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
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.
asked in Theory of Computation by Veteran (116k points) | 66 views

2 Answers

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( = n, then 

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

If ai+1 = 1, val( = n*3 + 1

If ai+1 = 2, val( = 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 (317 points)
0 votes

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

answered by Boss (18.6k points)

Related questions

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
49,443 questions
53,648 answers
70,909 users