Question

Construct a Moore machine that gives an output of 1 whenever the number of symbols in the input string read so far is divisible by 4 and an output of 0 otherwise.

Short answer

The Moore machine model is shown below.

Step-by-step solution

General form

Moore machine (Definition):

A Moore machine\({\bf{M = }}\left( {{\bf{S,}}\,\,{\bf{I,}}\,\,{\bf{O,}}\,\,{\bf{f,}}\,\,{\bf{g,}}\,\,{{\bf{s}}_0}} \right)\)consists of a finite set of states, an input alphabet I, an output alphabet O, a transition function f that assigns the next state to every pair of a state, and an input, an output function g that assigns an output to every state, and a starting state\({{\bf{s}}_0}\). A Moore machine can be represented either by a table listing the transitions for each pair of states and input and the outputs for each state, or by a state diagram that displays the states, the transitions between states, and the output for each state. In the diagram, transitions are indicated with arrows labelled with the input, and the outputs are shown next to the states.

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 Moore machine model

Given that, a Moore machine that gives an output of 1 whenever the number of symbols in the input string read so far is divisible by 4 and an output of 0 otherwise.

The input is a bit string.

Construction:

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

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

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

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

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

The output is 1 when we are at state \({{\bf{s}}_0}\) as the number of symbols so far is divisible by 4. The other states all have output 0.

We move from state \({{\bf{s}}_{\bf{0}}}\) to\({{\bf{s}}_{\bf{1}}}\), from \({{\bf{s}}_1}\) to\({{\bf{s}}_{\bf{2}}}\), from \({{\bf{s}}_{\bf{2}}}\)to\({{\bf{s}}_{\bf{3}}}\) , and from \({{\bf{s}}_{\bf{3}}}\) to\({{\bf{s}}_0}\) every time a digit is read. Moving from a state to another state is represented by an arrow, while the input is mentioned next to the arrow.

The model of the Moore machine is shown below.

Therefore, the result shows that the required Moore machine.