3
$\begingroup$

Construct a minimized Deterministic Finite Automaton that recognizes strings of 1's and 0's that are multiples of 3.

This was one of the questions asked in my cycle test.

What would be a correct interpretation to this question?

  1. Strings having a number of 0's and 1's that are multiple of 3, e.g.000111, 011010

  2. Strings of 0's and 1's which in binary notation is a multiple of 3, e.g. 11, 110

  3. Or any other radix notation, taking 0's and 1's, and checking if they are multiples of 3

$\endgroup$
3
  • 3
    $\begingroup$ I think 2, but I agree that the question is a bit ambiguous since a 'string' can't be a multiple of 3. $\endgroup$ Feb 20, 2017 at 7:42
  • $\begingroup$ @skankhunt42 1's and 0's need not necessarily be binary representation. I would argue its in decimal notation. then no string of 1's and 0's will be accepted $\endgroup$ Feb 20, 2017 at 8:12
  • 1
    $\begingroup$ @skankhunt42 "a 'string' can't be a multiple of 3." You're making a distinction without a difference. A representation of a number is essentially a number. If I ask you, "Is 45 divisible by 3?", you don't say "That doesn't make sense. 45 is a string of digits and 3 is a string of digits. There's no such thing as dividing a string by a string." $\endgroup$ Feb 20, 2017 at 8:38

2 Answers 2

1
$\begingroup$

If the question intends anything other than your option 2 (binary representations of natural numbers that are divisible by 3), then it is a badly written question.

If the qeustion meant strings in which the number of 0s and the number of 1s are both divisible by 3, it would have said that. It would be bizarre to have numbers whose digits are all 0s and 1s and intend some base other than binary without mentioning that.

$\endgroup$
1
  • $\begingroup$ Would the downvoters care to explain? $\endgroup$ Feb 23, 2017 at 1:13
0
$\begingroup$

To answer your question, I would go for option 2. But:

I think that's a badly written question without a clear interpretation.

I had a similar type of task in a course related to this, the task was about constructing a DFA for a language that accepts strings of a's and b's, where the amount of a's is divisible by 2 but not by 3.

In the case where the alphabet consists of characters the interpretation is clear in my opinion (in this particular task setting), but talking about "strings of 0's and 1's" is confusing.

$\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.