-2
$\begingroup$

design a DFA accepting the set of strings over the alphabet {0, 1} that when interpreted in reverse as a binary integer, are divisible by 3

$\endgroup$
1
$\begingroup$

This is a DFA for binary numbers divisible by three. your desirable language is reverse of this language.

enter image description here
For reversion of language of a DFA, you must reverse all of its transitions and change its initial state with its final state. in this case initial and final states are same, also its language is symmetric so all of transitions are symmetric.
Therefore you need only reverse all of its transitions are symmetric; so you don't need to do anything. above DFA is 1: https://i.stack.imgur.com/tiClh.jpg

$\endgroup$
0
$\begingroup$

Take a look here
https://stackoverflow.com/questions/39385971/how-to-know-if-a-binary-number-divides-by-3

This means that while your DFA consumes the number from right to left, you should keep track (by using different states) of whether your difference is divisible by three or not. Also, your DFA must keep track of whether you are in an odd or even position (again, using different states).

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