DFA Example on Division
For Complete YouTube Video: Click Here
In this class, We discuss DFA Example on Division.
The reader should have prior knowledge of DFA Examples. Click here.
Example: Design DFA that accepts binary numbers that are divided by 3.
The input symbols are Σ {0,1}
Logic:
In the DFA, we take three states q0,q1, and q2.
Why are we taking three states?
If we take any number and divide it by three, we get reminders 0,1, or 2.
three reminders are possible, so we take three states.
If we need to identify the numbers divisible by 5. we need to take five states. because of 5 reminders.
Follow the below steps to construct the logic.
The states are q0, q1, and q2.
If the binary number divide by three and the remainder is zero, we have to end up in state q0. This condition we follow.
Similarly, if the remainder is one, we need to end up in state q1.
If the remainder is two, we need to end up in state q2.
First step: Take binary number zero – 0.
We start from q0.
Zero modulus three will get zero. So we need to end up in state q0.
On the state q0, if we see the input character zero, we stay on state q0.
Second Step: Take binary number one –1.
One modulus three, we get reminder one.
On the state q0, if we see the input symbol one, we move to the q1 state.
Third Step: Take binary number two – 10
By taking the first input character one, we move to state q1,
The second input character is zero.
Two modulo three, we get two. So we need to end up in state q2.
On state q1, if we see the input character zero, we move to state q2.
Fourth Step: Take the binary number three – 11.
three modulus three is zero. So we need to end up in state q0.
Take the first input character and move to state q1.
On the state q1, we take the second input character.
On state q1, if we see input character zero. We move to state q0.
Fifth Step: Take the binary number four – 100.
Four modulus three reminder value 1. so we have to end up in state q1.
Take the first input character and move to state q1.
On state q1, we take the second input character and move to state q2.
The third input character is zero.
On the state q2, we take input character zero and move to state q1.
Sixth Step: Take the binary number five – 101.
five moduli three, we get two. So we need to end up in state q2.
Take the first two input characters and move to state q2.
On the state q2, if we see input character one, we move to state q2.
Similarly, we follow the above steps and construct the logic for any number.