Question

Draw an FA over {0, 1}which represent binaries of Integers only divisible by 3. Allleading 0’s are permissible. [10]

Answer 1

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