What makes a GOOD algorithm choose?
1 answer:
You might be interested in
Answer:
As we need to design the FA for the numbers divisible by 3, so we have to take the states as the remainders when we divide the numbers by 3.
Any number when divided by 3, gives remainder either 0 or 1 or 2. And the number gives remainder 0 is divisible by 3.
Let’s take
- state 0 for remainder 0.
- state 1 for remainder 1.
- state 2 for remainder 2.
So now lets count from 0:
Binary 0 = decimal 0 %3 = 0, so goes to state 0.
Binary 1 =decimal 1 %3 = 1, goes to state 1.
Binary 10 = decimal 2 %3 =2, goes to state 2.
Bianary 11 = decimal 3 %3 =0, goes to state 0.
Bianary 100 = decimal 4 %3 =1, goes to state 1.
Bianary 101 = decimal 5 %3 =2, goes to state 2.
And so on.
So here the state 0 will be the start state and also the final state.
Explanation:
So the FA is {{0,1,2}, {0,1}, δ, 0, {0}}
where δ(0, 0) = 0
δ(0, 1) = 1
δ(1, 0) = 2
δ(1, 1) = 0
δ(2, 0) = 1
δ(2, 1) = 2
