Skip to main content
Mathematics LibreTexts

14.5: The Machine of a Monoid

  • Page ID
    80568
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    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.

    Definition \(\PageIndex{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{.}\)

    Example \(\PageIndex{1}\)

    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 \(\PageIndex{1}\). 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].\)

    clipboard_eb6f73f09a57dc4e31cc62aa414f8f062.pngFigure \(\PageIndex{1}\): The machine of \([\mathbb{Z}_2;+_{2}]\)

    Example \(\PageIndex{2}\)

    The transition diagram of the monoids \(\left[\mathbb{Z}_2;\times _2\right]\) and \(\left[\mathbb{Z}_3;\times _3\right]\) appear in Figure \(\PageIndex{2}\).

    clipboard_ec12ddd668fd136247ffd94b51ad2f18b.pngFigure \(\PageIndex{2}\): The machines of \([\mathbb{Z}_2;\times_{2}]\) and \(\mathbb{Z}_{3};\times_{3}]\)

    Example \(\PageIndex{3}\)

    Let \(U\) be the monoid that we obtained from the unit-time delay machine (Example 14.4.2). 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 \(\PageIndex{3}\).

    clipboard_e16231856685687ab526113b5e78ce41e.pngFigure \(\PageIndex{3}\): Copy and Paste Caption here. (Copyright; author via source)

    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.

    14.5.1: Exercises

    Exercise \(\PageIndex{1}\)

    Draw the transition diagrams for the machines of the following monoids:

    1. \(\displaystyle \left[\mathbb{Z}_4;+_4\right]\)
    2. The direct product of \(\left[\mathbb{Z}_2;\times _2\right]\) with itself.
    Answer
    clipboard_efac3272bb2625461e4f5a90e1b503441.pngFigure \(\PageIndex{4}\): (a)
    clipboard_e6777df5d4d0f344d5553f8f8a674111c.pngFigure \(\PageIndex{5}\): (b)

    Exercise \(\PageIndex{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 \(\PageIndex{6}\). The same is true for the additive monoid of integers, as seen in Figure \(\PageIndex{7}\).

    clipboard_e5e73a9006a935f62c7d27f55bfb9dd49.pngFigure \(\PageIndex{6}\): An infinite machine \(B^*\)
    clipboard_e4229df79efe29293f745684b410ab873.pngFigure \(\PageIndex{7}\): An infinite machine \([\mathbb{Z};+]\)
    1. Draw a transition diagram for \(\{a, b, c\}\)
    2. Draw a transition diagram for \([\mathbb{Z}\times \mathbb{Z};\textrm{componentwise addition}]\text{.}\)
    3. Draw a transition diagram for \([\mathbb{Z};+]\) with generating set \(\{5,-2\}\text{.}\)

    This page titled 14.5: The Machine of a Monoid is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Al Doerr & Ken Levasseur via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.