Any finite monoid \([M;*]\) can be represented in the form of a finite-state machine with input and state sets equal to \(M\text{.}\) The output of the machine will be ignored here, since it would echo the current state of the machine. Machines of this type are called state machines. It can be shown that whatever can be done with a finite-state machine can be done with a state machine; however, there is a trade-off. Usually, state machines that perform a specific function are more complex than general finite-state machines.
Definition14.5.1.Machine of a Monoid.
If \([M;*]\) is a finite monoid, then the machine of \(M\text{,}\) denoted \(m(M)\text{,}\) is the state machine with state set \(M\text{,}\) input set \(M\text{,}\) and next-state function \(t : M\times M \to M\) defined by \(t(s, x) = s * x\text{.}\)
Example14.5.2.
We will construct the machine of the monoid \(\left[\mathbb{Z}_2;+_2\right]\text{.}\) As mentioned above, the state set and the input set are both \(\mathbb{Z}_2\text{.}\) The next state function is defined by \(t(s, x) = s +_2 x\text{.}\) The transition diagram for \(m\left(\mathbb{Z}_2\right)\) appears in Figure 14.5.3. Note how it is identical to the transition diagram of the parity checker, which has an associated monoid that was isomorphic to \(\left[\mathbb{Z}_2;+_2\right].\)
The machine of \([\mathbb{Z}_2;+_2]\)
Figure14.5.3.The machine of \([\mathbb{Z}_2;+_2]\)
Example14.5.4.
The transition diagram of the monoids \(\left[\mathbb{Z}_2;\times _2\right]\) and \(\left[\mathbb{Z}_3;\times _3\right]\) appear in Figure 14.5.5.
The machines of \([\mathbb{Z}_2; \times_2]\) and \([\mathbb{Z}_3;\times_3]\)
Figure14.5.5.The machines of \([\mathbb{Z}_2;\times_2]\) and \([\mathbb{Z}_3; \times_3]\)
Example14.5.6.
Let \(U\) be the monoid that we obtained from the unit-time delay machine (Example 14.4.3). We have seen that the machine of the monoid of the parity checker is essentially the parity checker. Will we obtain a unit-time delay machine when we construct the machine of \(U\text{?}\) We can’t expect to get exactly the same machine because the unit-time delay machine is not a state machine and the machine of a monoid is a state machine. However, we will see that our new machine is capable of telling us what input was received in the previous time period. The operation table for the monoid serves as a table to define the transition function for the machine. The row headings are the state values, while the column headings are the inputs. If we were to draw a transition diagram with all possible inputs, the diagram would be too difficult to read. Since \(U\) is generated by the two elements, \(T_0\) and \(T_1\text{,}\) we will include only those inputs. Suppose that we wanted to read the transition function for the input \(T_{01}\text{.}\) Since \(T_{01}=T_0T_1\text{,}\) in any state \(s, t\left(s, T_{01}\right) = t\left(t\left(s, T_0\right), T_1\right).\) The transition diagram appears in Figure 14.5.7.
Figure14.5.7.Unit time delay machine
If we start reading a string of 0’s and 1’s while in state \(T_{\lambda }\) and are in state \(T_{ab}\) at any one time, the input from the previous time period (not the input that sent us into \(T_{ab}\text{,}\) the one before that) is \(a\text{.}\) In states \(T_{\lambda }, T_0\) and \(T_1\text{,}\) no previous input exists.
ExercisesExercises
1.
Draw the transition diagrams for the machines of the following monoids:
\(\displaystyle \left[\mathbb{Z}_4;+_4\right]\)
The direct product of \(\left[\mathbb{Z}_2;\times _2\right]\) with itself.
Answer.
Figure14.5.8.(a)
Figure14.5.9.(b)
2.
Even though a monoid may be infinite, we can visualize it as an infinite-state machine provided that it is generated by a finite number of elements. For example, the monoid \(B^*\) is generated by 0 and 1. A section of its transition diagram can be obtained by allowing input only from the generating set. The monoid of integers under addition is generated by the set \(\{-1, 1\}\text{.}\) The transition diagram for this monoid can be visualized by drawing a small portion of it, as in Figure 10. The same is true for the additive monoid of integers, as seen in Figure 11.
