Tuesday, March 27, 2012

DFA of Binary number divisible by 5 (Details)


Question:  
Construct DFA  to accept set of all strings over alphabet set {0,1}( i.e, binary integer) is divisible by 5 eg 110, 1010,....?
OR
Construct DFA of strings whose binary interpretation is divisible by 5 over alphabet set {0,1}.
OR
Draw a DFA accepting the following languages over the alphabet {0,1}The set of all strings that, when interpreted as a binary integer, is a multiple of 5. 

Answer:

First we try to look the table, how a binary number is changed with respect to divisibility by 5, when 0 or 1 is placed at right:
---------------------------------------------------------------------------------------------------------
Number | Divisibility(Modulo) |  Inserted 0/(Modulo) | Inserted 1/(Modulo)    |
---------------------------------------------------------------------------------------------------------
0                Mod_0                          00 (Mod_0)                    01(Mod_1)
1                Mod_1                          10 (Mod_2)                    11(Mod_3)
10              Mod_2                          100 (Mod_4)                  101(Mod_0)
11              Mod_3                          110 (Mod_1)                  111(Mod_2)
100            Mod_4                          1000 (Mod_3)                1001(Mod_4)

101            Mod_0                          1010 (Mod_0)                1011(Mod_1)
110            Mod_1                          1100 (Mod_2)                1101(Mod_3)
111            Mod_2                          1110 (Mod_4)                1111(Mod_0)
1000          Mod_3                          10000 (Mod_1)              10001(Mod_2)
1001          Mod_4                          10010 (Mod_3)              10011(Mod_4)

1010          Mod_0                          10100 (Mod_0)              10101(Mod_1)
1011          Mod_1                          10110 (Mod_2)              10111(Mod_3)
1100          Mod_2                          11000 (Mod_4)              11001(Mod_0)
1101          Mod_3                          11010 (Mod_1)              11011(Mod_2)
1110          Mod_4                          11100 (Mod_3)              11101(Mod_4)

1111          Mod_0                          11110 (Mod_0)              11111(Mod_1)
10000        Mod_1                          100000 (Mod_2)            100001(Mod_3)
 -------------------------------------------------------------------------------------------------
And so on....


The State Transition Table is:

-----------------------------------------------------------------------------------
             Mod_0          Mod_1       Mod_2      Mod_3        Mod_4
------------------------------------------------------------------------------------
0           Mod_0           Mod_2      Mod_4      Mod_1       Mod_3
------------------------------------------------------------------------------------
1           Mod_1           Mod_3       Mod_0     Mod_2       Mod_4
------------------------------------------------------------------------------------


Finally the DFA of binary number divisible by 5 is :
 
Where MOD_0 is the final state.

2 comments: