Question

Construct a finite-state machine that gives an output of 1 if the number of input symbols read so far is divisible by 3 and an output of 0 otherwise.

Short answer

Therefore, the finite-state machine that gives an output of 1 if the number of input symbols read so far is divisible by 3 and an output of 0 otherwise machine model is shown below:

Step-by-step solution

General form

Finite-State Machines with Outputs (Definition):

A finite-state machine\({\bf{M = }}\left( {{\bf{S,}}\,\,{\bf{I,}}\,\,{\bf{O,}}\,\,{\bf{f,}}\,\,{\bf{g,}}\,\,{{\bf{s}}_0}} \right)\)consists of a finite set S of states, a finite input alphabet I, a finite output alphabet O, a transition function f that assigns to each state and input pair a new state, an output function g that assigns to each state and input pair output and an initial state\({{\bf{s}}_0}\).

Concept of input string and output:

An input string takes the starting state through a sequence of states, as determined by the transition function. As we read the input string symbol by symbol (from left to right), each input symbol takes the machine from one state to another. Because each transition produces an output, an input string also produces an output string.

Step 2: Construct a finite-state machine model

Given that, an output of 1, if the number of input symbols read so far, is divisible by 3 and an output of 0 otherwise.

Construction:

Let us consider the states\({{\bf{s}}_{\bf{i}}}\), where\({\bf{i = 0,1,2}}\).

\({{\bf{s}}_0}\)represents that we are at a position in the string that is divisible by 3.

\({{\bf{s}}_1}\)represents that we are at a position x in the string for which x mod\({\bf{3 = 1}}\).

\({{\bf{s}}_2}\)represents that we are at a position x in the string for which x mod\({\bf{3 = }}2\).

No matter what the input is, we move from state \({{\bf{s}}_0}\)to\({{\bf{s}}_1}\), from \({{\bf{s}}_1}\) to \({{\bf{s}}_2}\) , and from \({{\bf{s}}_2}\) to\({{\bf{s}}_0}\).

We only output a 1 every time we return to the state \({{\bf{s}}_0}\) as we are then at a position that is divisible by 3; else we will return to 0.

The model of the finite-state machine is shown below:

Therefore, the result shows the required finite-state machine.