1
$\begingroup$

enter image description here The first one is from unreputed youtuber whereas second one is from reputed university called adiuni course of theory of computation.

Now I know what that second figure means, it means it also accepts $\in$ as initial state=final state, but

  1. how I don't know that. This dfa should accept all binary divisble by 4. But how is nothing(it is not zero mind that) divisible by 4?

  2. Why I don't know that. I am making a dfa for binary numbers divisible by 4 and adiuni professor told that binary numbers that end with 00 are divisble by 4. So I googled about dfa ending with 00 and got this. I am personally more comfortable at first figure as it is more inituitive to me.

How is $\in$ divisible by 4? What does that even mean?

Improve this question
$\endgroup$
2
  • $\begingroup$ nothing [is not zero] (reminds me of difficulties ancient Greek philosophers are assumed to have had.) How do you know, how would I without access to the definitions (here: binary) to use? $\endgroup$
    – greybeard
    Nov 4, 2021 at 7:35
  • $\begingroup$ I would be inclined to agree with you, I don't know what divisibility even means for the empty string. $\endgroup$
    – awillia91
    Nov 6, 2021 at 23:59

1 Answer 1

Reset to default
1
$\begingroup$

The first DFA is correct, and the second is incorrect. When we say a string ends in 00 we imply that it must have at least two characters. So, it can't be the empty string, and it also can't be the single 0 string.

This dfa should accept all binary divisble by 4. But how is nothing(it is not zero mind that) divisible by 4?

I agree, and this is a good way of thinking about it. However, note that we aren't writing a DFA for the set of binary numbers divisible by 4 (that would include 0), but rather for the set of binary sequences which end in two zeros. So it is slightly different.

Improve this answer
$\endgroup$

Your Answer

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

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