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.
Wow I'm impressed!
ReplyDeleteThanks and that i have a dandy supply: House Renovation What To Do First house renovation ideas interior
ReplyDelete