Q: Draw a DFA of binary number divisible by 3 over alphabet {0,1}
Solution: First we try to look how a binary number changes when 0 or 1 is inserted at right side. (Mod_0, Mod_1, Mod_2 are remainder of a number when divisible by 3)
Inserted Digit Mod_0 Mod_1 Mod_2
---------------------------------------------------------------------------------------------
0 Mod_0 Mod_2 Mod_1
--------------------------------------------------------------------------------------------
1 Mod_1 Mod_0 Mod_2
-------------------------------------------------------------------------------------------
So the DFA is as:
Mod_0 is the final state.
No comments:
Post a Comment