MATH 1120 Quiz: MATH 1120 Cornell WARMUP2018 Quiz5 1Solutions
Document Summary
More formally, if we let e be the number of 1"s in even positions and u be the number of 1"s in odd positions, then (e-u) mod 3 = 0. For example, 1407 has the binary representation 10101111111 for which e=6 and u=3, (6-3) mod 3=0, and thus it is divisible by 3. Use this to construct a dfa that accepts strings of 0"s and 1"s such that the corresponding natural number is divisible by 3. That is, your dfa should accept any string such that (e-u) mod 3 = 0 and reject any other string. Assume that your dfa reads its input from right to left, that is with least significant bit first (or equivalently assume that the string is reversed before being passed to the dfa). For full credit you should create correct a dfa with the smallest possible number of states (which is 3), however a correct dfa with 6 states will receive substantial partial credit.
