To design a Finite State machine

Question

Design a FSM for a binary number in which the input is valid if no. of 0's divisible by 5 and no. of 1's divisible by 3

Answer 1

$\def\z{\mathtt{0}}\def\o{\mathtt{1}}$Consider part of the problem, where we are only interested in the number of $\o$s in the input. When designing a FSM, a good plan of attack is to decide the states, then figure which should be the start state, which should be final states, and finally determine the transitions between the states.

Specifying the states. In this case, we'll let the state $q_i$ correspond to "the input so far has a number $n$ of $\o$s that has remainder $i$ when divided by 3". We'll have states $q_0, q_1$, and $q_2$, so for example having seen 8 ones we should be in state $q_2$, and having seen 9 ones we should be in state $q_0$. In terms of modular arithmetic, after seeing $n$ ones, we want to be in state $i$ where $i\,\equiv\pmod{n}$.

Determining start and final states. Before we've seen any input, we've seen zero ones, so $q_0$ should be the start state. We want to accept any string where the number of ones is a multiple of 3, so $q_0$ will also be a final state.

Deciding on the transitions. From state $q_0$, for example, if we see another $\o$ in the input, we want to go to state $q_1$. If we're in state $q_0$ and the next input character is a $\z$ we haven't changed the number of ones, so we want to stay in state $q_0$. Do the same process for states $q_1$ and $q_2$ and you're done, having completely specified the FSM.

For your problem we'll also have to consider the number of zeros in the input, so you'll have more states, corresponding to the possible remainders of ones mod 3 and zeros mod 5, but the process should be clear enough that you can fill in the details.

---

Now we want to do the same thing, but also keep track of the counts of both the zeros and the ones in the input. Since we're only interested in the remainder of the number of zeros when divided by 5 and the number of ones when divided by 3, there will be fifteen possibilities. Let the states be labeled by ordered pairs $(p, q)$, where $p=0,1,2,3,4$ and $q=0,1,2$.

Now suppose we had seen the input $\mathtt{0100101101001}$ so far. Then, since there were 7 $\z$s and 6 $\o$s, we'd want to be in state $(2, 0)$ since the remainder of 7 divided by 5 is 2 and the remainder of 6 divided by 3 is 0.

So our FSM will have 15 states, $(0, 0), (0, 1), (0, 2),(1, 0), \dots,(4, 2)$. The start state, before we've seen any input, will be $(0,0)$ and this will also be the only final state, since in this state the number of zeros seen will be a multiple of 5 and the number of ones will be a multiple of 3. Now all you have to do is decide on the transitions.

For example, suppose we were in state $(2, 0)$. If we next encounter a zero, we'll switch to state $(3,0)$ and if we encounter a one, we'll switch to state $(2, 1)$. Do this for all fifteen states and you'll have your automaton. As Brian noted in his answer, what you're doing here is known as taking the Cartesian product of two simpler FSMs, one for the zeros in the input and one for the ones. This construction isn't given much attention in many texts, but can be quite helpful in situations like this.

Answer 2

HINT: Label your states with the ordered pairs in $\{0,1,2,3,4\}\times\{0,1,2\}$, and try to design the automaton so that it is in state $q_{k,\ell}$ precisely when the number of $1$’s read so far leaves a remainder of $k$ when divided by $5$ and the number of $0$’s read so far leaves a remainder of $\ell$ when divided by $3$. The initial state must then be $q_{0,0}$, and you should have no trouble figuring out what state(s) should be accepting.

In general in these problems you should set up the states to keep track of the critical information. To keep track of whether you’ve seen an odd number of $0$’s for instance, you need just two states, one for when you’re read an even number of $0$’s, and one for when you’ve read an odd number. You might think that you could get away with two states to tell whether you’ve read a multiple of $3$ $0$’s, one for when you have and the other for when you haven’t, but if you think about it for a bit, you’ll see that that won’t work: how can you tell when to move from the haven’t state to the have state and when to stay in the haven’t state? But you can use three states, one for when you’ve seen a multiple of $3$ $0$’s, one for when you’ve seen $1$ more than a multiple of $3$ $0$’s, and a third for when you’ve seen $2$ more than a multiple of $3$ $0$’s: each $0$ that you read just moves you one state around the ring.

Here you have to keep track of two things, so let the (label of the) state that you’re in convey two pieces of information; using the Cartesian product of two sets of simpler labels is one easy way to accomplish that.