Wednesday, April 25, 2012

DFA(Deterministic Finite Automaton) of Binary Number Divisible by 3




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