0
$\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$
  • 3
    $\begingroup$ My favourite automaton ! $\endgroup$ – Hendrik Jan Jan 4 '17 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 '17 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$ – Hendrik Jan Jan 4 '17 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$ – Hendrik Jan Jan 4 '17 at 15:56
  • $\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 '17 at 18:43
4
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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