I'm trying to write an inductive proof to show that my DFA accepts all binary strings which are divisible by 4 (divisible by $100_2$). Part of this proof is describing the language which machine $M$ accepts.
So far I've written the language as:
$\{0, 1\}^*\{00\}$
Because any binary string when interpreted as a binary number is divisible by 4 iff its last two digits are $00$.
However I'd like to exclude the empty string from this.
Should I write it as $(\{0, 1\}^* – \{\varepsilon\})\{00\}$? To get rid of the empty string from the set of all binary strings.
Best Answer
The most natural representation of numbers as binary strings is to represent $0$ by the empty string and all other numbers by a string starting with $1$. In this way, the numbers divisible by $4$ can be represented by the language $1\{0,1\}^*00 \cup \{\epsilon\}$.
EDIT (answer to the comments). The problem is that the sentence "binary string when interpreted as a binary number" is not clear, because for instance, $011$ is a binary string but is not a binary number. If you decide to remove all the leading $0$'s, then each number has infinitely many binary strings representing it. For instance, the number $3$ would be represented by all binary strings of the form $0^k11$, with $k \geqslant 0$. Similarly, the number $0$ would be represented by all binary strings of the form $0^k$, with $k \geqslant 0$. Note that the case $k = 0$ corresponds to the empty string. If you adopt this convention, the solution should be modified to $$ 0^*\bigl(1\{0,1\}^*00 \cup \{\epsilon\}\bigr) $$