1
$\begingroup$

I have found in a book the example of how to make a FA that accepts those numbers that are divisible by 3, that means that n mod 3=0. In the example the author used the binary representation of the number to be evaluated. The resulting automata is:

enter image description here

The states represent the probable remainders, that could be 0, 1 or 2. Some additional explanation is in the following part:

enter image description here

I have tried the following examples to test this automata:

  • If I try to do 6 mod 3 that will result in 0, so I will go from the initial state (upper part of the figure) to the acceptance state, that is because the modulus is 0.
  • If I try 5 mod 3 or 101 mod 11 that would be 2, which in binary is 10. If I want to apply again 2 mod 3. I will end up again with 2 and not reaching an acceptance state. From the upper part I followed the path 1--state 1--0--state 2. What happens there? it just stays in that state 2?

I just do not have a clear picture of how to test this FA for example with an input of 81 mod 3, does it make partial divisions? When I try to follow it I end up in an acceptance state even before finishing to evaluate the remainder.

Any help?

$\endgroup$
5
  • 4
    $\begingroup$ My favourite automaton ! $\endgroup$ Jan 4, 2017 at 15:41
  • 1
    $\begingroup$ @HendrikJan your solution was shorter, I am trying to get a full grasp of your solution $\endgroup$
    – Layla
    Jan 4, 2017 at 15:45
  • 1
    $\begingroup$ My solution is shorter because it also accepts strings starting with $0$. If one does not believe those represent numbers then the solution you present is right. The automaton is keeping track of the number represented by the string read, modulo three. So reading the next letter means multiplying by two plus the letter read. That is all the machine does. like the value of "x0" means two times the value "x" and the value of "x1" is two times the value of "x" plus one, where "x" is a binary number/string. $\endgroup$ Jan 4, 2017 at 15:49
  • 1
    $\begingroup$ By the way, what book you are using? Because (A) I am just very curious, and (B) It is is customary to credit sources. $\endgroup$ Jan 4, 2017 at 15:56
  • 1
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$
    – Raphael
    Jan 4, 2017 at 18:43

3 Answers 3

5
$\begingroup$

I believe you are misunderstanding the way finite automata work. A finite automaton accepts a language, i.e. a subset of the finite strings of a given finite alphabet. In your case, the accepted language is the set of strings made of $0$ and $1$ which encode a well-formed multiple of $3$.

Given a string, imagine placing a token on the initial state, then for each character of the string, left to right, move the token along the transition labelled $0$ or $1$, according to which character you read.

After having consumed each character of the string, the automaton accepts if and only if the token is on one of the accepting states.

Considering your automaton, intuitively, the top three states determine whether the string encodes a well-formed number (i.e. a string that starts with $1$ or is exactly $0$, for instance, $1000$ is valid, but $000$ isn't) while the bottom three determine whether or not it is divisible by $3$ using elementary number theory.

$\endgroup$
2
$\begingroup$

We want to design a Deterministic Finite Automaton (DFA) that accepts Binary Representation of Integers which are divisible by 3.

Now, by accept, in layman terms, we can say that when we are done with scanning string, we should be in one of the multiple possible Final States.

More Formally, Let $w = a_1a_2…a_n$ be a string over the alphabet $Σ$. The automaton accepts the string $w$ if a sequence of states, $r_0, r_1, …, r_n$, exists in $Q$ with the following conditions:

  1. $r_0 = q_0$
  2. $r_{i+1} = δ(r_i, a_{i+1})$, for $i = 0, …, n − 1$
  3. $r_n \in F$

In brief, A word $w=a_{1}a_{2}...a_{n}\in \Sigma ^{*}$ is an accepting word for the automaton if $\overline {\delta }(q_{0},w)\in F$, that is, if after consuming the whole string $w$, the machine is in an accept state.

Approach : Essentially, we need to divide the Binary Representation of Integer by 3, and track the remainder. If after consuming/scanning [From Left to Right] the entire string, remainder is Zero, then we should end up in Final State, and if remainder isn't zero we should be in Non-Final States.

Now, DFA is defined by Quintuple$/5$-Tuple $(Q,q_0,F,\Sigma,\delta)$. We will obtain these five components step-by-step.


$Q$ : Finite Set of States
We need to track remainder. On dividing any integer by $3$, we can get remainder as $0,1$ or $2$. Hence, we will have Three States $Z, V$ and $T$ respectively. $$Q=\{Z,V,T\}$$ If after scanning certain part of Binary String, we are in state $Z$, this means that integer defined from Left to this part will give remainder $Z$ero when divided by $3$. Similarly, $V$ for remainder $1$, and $T$ for remainder $2$.
$\hspace{6cm}$enter image description here

Now, we can write these three states by Euclidean Division Algorithm as

$Z=3m\\V=3m+1\\T=3m+2\\ \text{where } m \in \mathbb{Z} \text{ (Set of Integers)}$


$q_0$ : an initial/start state $q_0\in Q$
Now, start state can be thought in terms of empty string $(\varepsilon)$. An $\varepsilon$ directly gets into $q_0$.
Now, what remainder does $\varepsilon$ gives when divided by $3$?

Now, we can append as many $0s$ in left hand side of a Binary Number. In the similar fashion, we can append $\varepsilon$ in left hand side of a Binary String. Thus, $\varepsilon$ in left can be thought of as 0. And $0$ when divided by $3$ gives remainder $0$. Hence, $\varepsilon$ should end in State $Z$. But $\varepsilon$ ends up in $q_0$.

Thus, starting state should be

$$q_0=Z$$ $\hspace{6cm}$enter image description here


$F :$ a set of accept states, $F\subseteq Q$
Now we want all strings which are divisible by $3$, or which gives remainder $0$ when divided by $3$, or which after complete scanning should end up in state $Z$, and gets accepted. Hence, $$F=\{Z\}$$
$\hspace{8cm}$enter image description here


$\Sigma :$ Alphabet (a finite set of input symbols)
Since we are scanning/reading a Binary String. Hence,

$$\Sigma=\{0,1\}$$


$\delta :$ Transition Function $(δ : Q × Σ → Q)$
Now this $\delta$ tells us that if we are in state $x\in Q$ and next input to be scanned is $y\in \Sigma$, then at which state $z\in Q$ should we go.

In context of this problem, if the string upto this point gives remainder $1/V$ when divided by $3$, and if we append $1$ to string, then what remainder will resultant string give.

Now, this can be analyzed by observing how magnitude of a binary string changes on appending 0 and 1.

In Decimal (Base-$10$), if we add/append $0$, then magnitude gets multiplied by

$10$
Example : $64$, on appending $0$ it becomes $640$

Also, if we append $7$ to decimal, then

Magnitude gets multiplied by $10$, and then we add $7$ to multiplied magnitude.

In Binary (Base-$2$), if we add/append $0$, then magnitude gets multiplied by

$2$ (The Positional Weight of each Bit get multiplied by $2$)
Example : $(1010)_2$ [which is $(10)_{10}$], on appending $0$ it becomes $(10100)_2$ [which is $(20)_{10}$]

Similarly, In Binary, if we append $1$, then

Magnitude gets multiplied by $2$, and then we add $1$.
Example : $(10)_2$ [which is $(2)_{10}$], on appending $1$ it becomes $(101)_2$ [which is $(5)_{10}$]

Thus, we can say that for Binary String $x$,

  • $x0=2|x|$
  • $x1=2|x|+1$

We will use these relation to analyze three States

  • Any string in $Z$ can be written as $3m$

    • On $0$, it becomes $2(3m)$, which is $3(2m)$, nothing but state $Z$.
    • On $1$, it becomes $2(3m)+1$, which is $3(2m)+1$, that is $V$.
      [This can be read as if a Binary String is presently divisible by $3$, and we append $1$, then resultant string will give remainder as $1$]
      $\hspace{3cm}$enter image description here
  • Any string in $V$ can be written as $3m+1$

    • On $0$, it becomes $2(3m+1)=6m+2$, which is $3(2m)+2$, state $T$.
    • On $1$, it becomes $2(3m+1)+1=6m+3$, which is $3(2m+1)$, state $Z$.
      [If $m\in \mathbb{Z}$ (Set of Integers), then $(2m+1)\in \mathbb{Z}$]
      $\hspace{3cm}$enter image description here
  • Any string in $T$ can be written as $3m+2$

    • On $0$, it becomes $2(3m+2)=6m+4$, which is $3(2m+1)+1$, state $V$.
    • On $1$, it becomes $2(3m+2)+1=6m+5$, which is $3(2m+1)+2$, state $T$.
      $\hspace{3cm}$enter image description here

Hence, the final DFA combining Everything
enter image description here


To Test $6$, which in binary is $110$

  • On $Z$, scan $1$, go to $V$.
  • On $V$, scan $1$, go to $Z$.
  • On $Z$, scan $0$, go to $Z$.

String Consumed. We are in $Z\in F$. Hence $110$ accepted.

To Test $5$, which in binary is $101$

  • On $Z$, scan $1$, go to $V$.
  • On $V$, scan $0$, go to $T$.
  • On $T$, scan $1$, go to $T$.

String Consumed. We are in $T\notin F$. Hence $101$ rejected.

To Test $81$, which in binary is $1010001$

  • On $Z$, scan $1$, go to $V$.
  • On $V$, scan $0$, go to $T$.
  • On $T$, scan $1$, go to $T$.
  • On $T$, scan $0$, go to $V$.
  • On $V$, scan $0$, go to $V$.
  • On $V$, scan $0$, go to $V$.
  • On $V$, scan $1$, go to $Z$.

String Consumed. We are in $Z\in F$. Hence $1010001$ accepted.


$\endgroup$
0
$\begingroup$

Hint:

If the remainders of $n$ by $3$ are $0, 1, 2$, then the remainders of $n$ followed by zero (i.e. $2n$) are $0, 2, 1$, and the remainders of $n$ followed by one (i.e. $2n+1$) are $1,0,2$.

This explains the transitions between the bottom states marked $0,1,2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.