Construct a DFA with the input alphabet = f0; 1g which accepts all inputs (in bi

Question

Construct a DFA with the input alphabet = f0; 1g which accepts all inputs (in binary
numbers) that are divisible by 5 (and rejects all other inputs).

Explanation / Answer

There can be four cases for previous x(sequence of binary number until now ) CR = current Remainder = (2*previous remainder + New bit) mod 5 First :- Remainder 0 Then if 0 comes Number = 2*previous + 0 => CR = 0 (First State) Then if 1 comes Number = 2*previous + 1 => CR = 1 (Second State) Second :- Remainder 1 Then if 0 comes Number = 2*previous + 0 => CR = 2 (Third state) Then if 1 comes Number = 2*previous + 1 => CR = 3 (Fourth state) Third :- Remainder 2 Then if 0 comes Number = 2*previous + 0 => CR = 4 (Fifth State) Then if 1 comes Number = 2*previous + 1 => CR = 0 (First State) Fourth :- Remainder 3 Then if 0 comes Number = 2*previous + 0 => CR = 1 (Fist State) Then if 1 comes Number = 2*previous + 1 => CR = 2 (Second State) Fifth :- Remainder 4 Then if 0 comes Number = 2*previous + 0 => CR = 3 (Third State) Then if 1 comes Number = 2*previous + 1 => CR = 4 (Fourth State) Start State - first Accept State - first All state transition are given and all start and accept state are given. Hence DFD can be drawn.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---