State Machines and Hypergroups

Abstract

State machines are a type of mathematical modeling tool that is commonly used to investigate how a system interacts with its surroundings. The system is thought to be made up of discrete states that change in response to external inputs. The state machines whose environment is a two-element magma are investigated in this study, focusing on the case when the magma is a group or a hypergroup. It is shown that state machines in any two-element magma can only have up to three states. In particular, the quasi-automata and quasi-multiautomata state machines are described and enumerated.

1. Introduction

The state machines and the hypergroups are mathematical achievements of the twentieth century. The state machines are mathematical models which are mostly used for the study of actual physical or behavioral processes. Their roots can be traced back to mathematical logic and they are the primary and major components of Computer Theory. Alan Mathison Turing (1912–1954) developed his theoretical universal-algorithm machine to address the question of whether an algorithm for providing proofs whenever they do exist can be found and he discovered that some tasks which this abstract machine is expected to be able to perform are impossible even for it. The usefulness of the state machines quickly began to spread in other sciences as well. For example, Warren Sturgis McCulloch (1898–1969) and Walter Harry Pitts (1923–1969) created a mathematical model in neuroscience [1]. The model they constructed for a “neural net” was a state machine of the same nature as Turing’s. Stephen Cole Kleene (1909–1994) later elaborated their model [2], while Noam Chomsky created mathematical models in linguistics for the description of languages [3,4]. The rapid development of technology in the twentieth century has made it possible to materialize such theoretical machines by creating the computers. This development fulfilled the timeless dream of mankind, to create machines like the Antikythera mechanism of the Hellenistic era (the earliest known analog computer, dated back to the second century BC [5,6,7]), and the mechanical calculating devices created by Blaise Pascal (1623–1662), by Gottfried Wilhelm von Leibniz (1646–1716), by Charles Babbade (1792–1871) and his co-worker Ada Augusta (1815–1852), the daughter of poet Lord Byron, all of which were as powerful as their respective technologies would allow.

The basic building blocks of a state machine are their internal qualities which are named internal states. The internal states are reacting to certain changes in their environment and this reaction causes state transitions. In the general case, it does not matter what the states and the environment of a state machine really are.

For example, in biology, we can consider the state of a cell in its environment, which consists of certain chemical and physical conditions, such as PH, temperature, light and so on. When these chemicals do not remain within a range of concentrations and/or the physical conditions exceed a threshold value, the cell changes its behavior, e.g., a plant cell performs photosynthesis under the “input” of sunlight.

Also, a population group or a business can move to a new state when the economic and social changes in its environment cross a certain threshold.

Respectively in an electronic system which involves various electrical components, the flow of electric current can activate some of these components and the system can switch from one state to another. In fact, as in the case of some circuits with flip-flops, the new state depends on both, the input pulse and the previous state of the circuit.

So, the same environmental change (input) can shift the system into different states, depending on its previous state (condition).

A lot of ink has been shed on the research and study of the behavior of such systems, both living and non-living. In this paper, we approach this issue from a different perspective, i.e., we will address the question of how many different state machines can “survive” or can be acceptable in a given environment. Undoubtedly, the interaction between a system and its environment can be vastly complicated and it still remains an area that needs to be understood, if we wish to be in a position to predict the behaviour of the system and perceive the level of the environmental constraints it can endure as well as their impact on it.

We will attempt this approach with the tools of abstract Algebra, which is the most extensively used branch of Mathematics in the study of the state machines. So, in this paper, the environment is a set equipped with a rule of synthesis such that the result of the synthesis of any two elements is one or more elements. In Éléments de Mathématique, Algèbre [8], Nicolas Bourbaki used the Greek word magma, which comes from the verb μάσσω (=knead), to indicate such a set, while in [9] this notion was generalized so as to include more structures. Here, we use the magma of two elements, which is the environment of the binary state machines, like the 0–1 environment which is used in the digital technology. The interaction of the environment on the states is modeled algebraically via the different types of the associativity.

Sometimes, algebraic tools had been developed before even the relevant questions were asked and this is one of the most fascinating aspects of mathematics: to give the answers long before the rest of the world realizes why they should ask the questions.

During the 20th century, Algebra itself faced, and on most occasions overcame, many difficult and serious challenges that were deriving from various mathematical and not only areas, such as the Theory of Equations, Geometry, Topology, Quantum Mechanics, Chemistry, etc. Also, the 20th century put an end to the paradise of determinism. David Hilbert’s (1862–1943) visions collapsed under Kurt Gödel’s (1906–1978) work. Quantum Mechanics, the uncertainty principle of Werner Heisenberg (1901–1976), the axiomatic foundation of probability by Andrey Kolmogorov (1903–1987) made uncertainty inherent in science and brought into existence its mathematics. In this direction, Frédéric Marty (1911–1940) in a series of three papers [10,11,12] introduced the hypergroup in Algebra and gave some of its initial properties. His untimely death during World War II, while serving as a French Army officer, did not allow him to write more papers. However, the aforementioned three were enough to bring into being the Hypercompositional Algebra. The fundamental notion of the Hypercompositional Algebra is the hypercomposition, that is, a law of synthesis of any two elements, which yields a set of elements instead of a single element only.

The introduction of Hypercompositional Algebra into Computer Theory occurred in the G.G. Massouros Ph.D. thesis [5], under the supervision of J. Mittas (1921–2012). There followed more papers by the same author and Ch. Massouros, e.g., [13,14,15,16,17,18,19,20,21], as well as other researchers such as J. Chvalina [22,23,24,25,26,27,28], L. Chvalinová [22], Š. Hošková-Mayerová [24,25], M. Novák [26,27,28,29,30,31,32], S. Křehlík [26,27,29,30,31,33], M.M. Zahedi [34], M. Ghorani [34,35], D. Heidari and S. Doostali [36], R.A. Borzooei et al. [37]. In relation to this subject, there are applications of the Hypercompositional Algebra in graph theory, artificial intelligence, cryptography, sensor networks and many more that, indicatively, can be found in [38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60]. Also, results in the above areas, up to the date it was published, can be found in P. Corsini and V. Leoreanu’s book [61].

The following section presents the necessary preliminary notions for the self-sufficiency of the paper. The third section contains a study of operators’ and hyperoperators’ actions and the way they define hypercompositional structures in the set on which they operate. The fourth paragraph focuses on the detailed study of the magma of two elements, which is the environment of the binary state machines. The next (fifth) paragraph is dedicated to the analysis of the binary state machines, when their environment has the structure of a group or a hypergroup. The quasi-automata and quasi-multiautomata that can exist in such an environment are studied and enumerated.

2. Preliminaries

The fundamental notion of the Hypercompositional Algebra is the hypercomposition, that is, a law of synthesis which yields a set of elements instead of a single element, when applied on any two elements. More specifically, we have the definitions [9]:

Definition 1.

Let $E$ be a non-void set. A mapping from $E\times E$ into $E$ is called a composition on $E$, while a mapping from $E\times E$ into the power set $P\left(E\right)$ of $E$ is called a hypercomposition on $E$. A hypercomposition is called partial, if $ab=\varnothing$, for some $a,b$ in $E$. A set enriched with a composition or a hypercomposition is called a magma.

The above definition, which was introduced in [9], extends the definition of the magma given by Nicolas Bourbaki [8] in order to include laws of synthesis which are hypercompositions on a set $E$.

Let $\left(E,\perp \right)$ be a magma. For any two non-void subsets $X,Y$ of $E$, $X\perp Y=\left\{x\perp y\in E|x\in X, y\in Y\right\}$, if $\perp$ is a composition and $X\perp Y={\displaystyle \underset{x\in X, y\in Y}{\cup }\left(x\perp y\right)}$, if $\perp$ is a hypercomposition.

If $X$ or $Y$ is empty, then $X\perp Y$ is empty. If $a\in E$, we usually write $a\perp Y$ instead of $\left\{a\right\}\perp Y$ and $X\perp a$ instead of $X\perp \left\{a\right\}$. In general, the singleton $\left\{a\right\}$ is identified with its member $a$. Sometimes it is convenient to use the relational notation $A\approx B$ to assert that subsets $A$ and $B$ have a non-void intersection. Then, as the singleton $\left\{a\right\}$ is identified with its member $a$, the notation $a\approx A$ or $A\approx a$ is used as a substitute for $a\in A$. The relation $\approx$ may be considered as a weak generalization of the equality, since, if $A$ and $B$ are singletons and $A\approx B$, then $A=B$. Thus, $a\approx b\perp c$ means $a=b\perp c$, if the synthesis is a composition and $a\in b\perp c$, if the synthesis is a hypercomposition. This notation is extensively used when it is not necessary to distinguish between a composition or a hypercomposition with respect to a law of synthesis.

Definition 2.

A law of synthesis$\left(x,y\right)\to x\perp y$on a set$E$is called associative if the property,

$$\left(x\perp y\right)\perp z=x\perp \left(y\perp z\right)$$

is valid, for all elements  $x,y,z$ in  $E$, while it is called reproductive if for all elements  $x$ in $E$ the equality

$$x\perp E=E\perp x=E$$

holds.

Definition 3.

An associative magma is called α semigroup if the law of synthesis on the magma is a composition, while it is called α semihypergroup if the law of synthesis is a non-partial hypercomposition.

Definition 4.

A reproductive magma is called α quasigroup if the law of synthesis on the magma is a composition, while it is called α quasihypergroup if the law of synthesis is a non-partial hypercomposition.

Definition 5.

An associative and reproductive magma is called α group if the law of synthesis on the magma is a composition, while it is called α hypergroup if the law of synthesis is a hypercomposition.

The above Definition 5 appeared in [9], which also contains a detailed presentation of the fundamental properties that derive from the axioms of the associativity and the reproductivity in groups and hypergroups. Among other things, in [9] it is proved that:

Theorem 1.

If G is a group, then:

i. 

there exists an element$e\in G$such that$ea=a=ae$for all$a\in G$

ii. 

for each element$a\in G$there exists an element$a^{\prime }\in G$such that$a^{\prime }a=e=a{a}^{\prime }$

Theorem 2.

If$H$is a hypergroup, then:

$ab\ne \varnothing$for all$a, b\in H$

Thus, the hypercomposition in a hypergroup cannot be partial. In this paper, we will consider only non-partial hypercompositions.

It is very common in the bibliography to enrich a magma with the axiom of associativity. Besides, another equality that can be valid in the successive synthesis of the magma’s elements is the inverted associativity. Recall that a composition or a hypercomposition on a non-void set E is called left inverted associative if

$$\left(a\perp b\right)\perp c=\left(c\perp b\right)\perp a, \mathrm{for} \mathrm{every} a,b,c\in E,$$

while it is called right inverted associative if

$$a\perp \left(b\perp c\right)=c\perp \left(b\perp a\right), \mathrm{for} \mathrm{every} a,b,c\in E.$$

The notion of the inverted associativity was initially conceived by Kazim and Naseeruddin [62]. A magma equipped with a left inverted associativity is called left almost semigroup if the law of synthesis is a composition, while it is called left almost semihypergroup if the law of synthesis is a hypercomposition. The terminology is analogous for the right inverted associative magma.

Definition 6.

A reproductive magma which satisfies the axiom of the left inverted associativity is called a left almost-group (LA-group) when the law of synthesis on the magma is a composition, while it is called α left almost-hypergroup (LA-hypergroup) when the law of synthesis is a hypercomposition. A reproductive, right inverted associative magma is called a right almost-group (RA-group) or a right almost-hypergroup (RA-hypergroup) when the law of synthesis is a composition or a hypercomposition respectively.

Apparently, if the law of synthesis is commutative, then the almost left or almost right groups and hypergroups are groups and hypergroups, respectively. However, it is possible for both associativity and inverted associativity to be valid in a magma. Such cases can be found in the examples of [63], which presents a detailed study of the left/right almost-hypergroups. For the quasi-canonical LA-hypergroups, see [64].

Every law of synthesis in a magma induces two new laws of synthesis. If the law of synthesis is written multiplicatively, then the two induced laws are:

$$a/b=\left\{x\in E | a\approx xb\right\} \mathrm{and} b\backslash a=\left\{x\in E | a\approx bx\right\}$$

Thus $x\approx a/b$ if and only if $a\approx xb$ and $x\approx b\backslash a$ if and only if $a\approx bx$. In the case of a multiplicative magma, the two induced laws are called inverse laws and they are named right division and left division, respectively. If the magma is commutative, it is obvious that the right and left divisions coincide.

Directly connected to the induced laws of synthesis is the transposition axiom, which was firstly introduced by W. Prenowitz (1906–2000) for the study of geometry with the tools of Hypercompositional Algebra (e.g., [65]) and afterwards it was generalized by J. Jantosciak (1942–2017) in [66].

Definition 7.

A magma$E$is called α transposition magma if it satisfies the axiom:

$$b\backslash a\approx c/d implies ad\approx bc, for all a,b,c,d\in E$$

It is obvious that in a transposition magma the following implication

$$a\backslash b\approx d/c \Rightarrow ad\approx bc, for all a,b,c,d\in E$$

is valid as well. In [9], the above implications reversed and so we have the two reverse transposition axioms:

• Weak reverse transposition axiom:

$$ad\approx bc implies b\backslash a\approx c/d or a\backslash b\approx d/c, for all a,b,c,d\in E$$

• Strong reverse transposition axiom:

$$ad\approx bc implies b\backslash a\approx c/d and a\backslash b\approx d/c, for all a,b,c,d\in E$$

However, the following property also applies:

$$ad\approx bc \iff a\backslash b\approx d/c or b\backslash a\approx c/d , for all a,b,c,d\in E$$

This axiom was named bilateral transposition axiom [9].

Special notation: In the following pages, in addition to the typical algebraic notations, we are using Krasner’s notation for the complement and difference. So, we denote by A··B the set of elements that are in the set A, but not in the set B.

3. Action of a Magma on a Set

Let $E$ and $S$ be two non-empty sets. A mapping of $E$ into the set $S^S$ of the mappings of $S$ into itself is called an action of $E$ on $S$. Let $a\to {\delta }_a$ be an action of $E$ on $S$. The mapping $\delta$ of $S\times E$ to $S$ such that $\delta \left(s,a\right)={\delta }_a\left(s\right)$ is an external law of composition on $S$, with $E$ being the operating set. $\delta$ is called the law of right action of $E$ on $S$. The law of left action of $E$ on $S$ is defined in a similar way. The element ${\delta }_a\left(s\right)$ is also called the transform of $s$ under $a$. Ιt is usually denoted by a right (resp. left) multiplicative notation $sa$ (resp. $as$). The elements of $E$ are called operators.

A mapping $\stackrel{⌢}{\delta }$ of $S\times E$ to the power set $P\left(S\right)$ of $S$ is an external law of hypercomposition on $S$. Then, the elements of $E$ are called hyperoperators [67]. If $a\in E$ is a hyperoperator, then the multiplicative notation $sa$ (resp. $as$) signifies an element of $P\left(S\right)$, that is, $sa\subseteq S$ (resp. $as\subseteq S$).

A subset $T$ of $S$ is called stable under the action $a\to {\delta }_a$ of $E$ on $S$ if ${\delta }_a\left(T\right)\subseteq T$ for all $a\in E$. The intersection of a family of stable subsets of $S$ under a given action is a stable subset of $S$ as well. Therefore, if $X$ is any subset of $S$, there exists a smallest stable subset of S that contains it. This subset is said to be generated by $X$ and it consists of the elements $\left({\delta }_{a_1}\circ {\delta }_{a_2}\circ \cdots \circ {\delta }_{a_n}\right)\left(x\right)$, where $x\in X$, $n>0$, $a_i\in E$ for all $i$.

Definition 8.

An element$s_2$of$S$is called connected to an element$s_1$of$S$if there exists an element$a$of$E$such that${\delta }_a\left(s_1\right)=s_2$.

It must be mentioned that $s_2$ being connected to $s_1$ does not necessarily imply that $s_1$ is connected to $s_2$. If $s_2$ is connected to $s_1$, there may be a sequence $a_1,a_2,\dots ,a_n$ of elements of $E$ such that $\left({\delta }_{a_1}\circ {\delta }_{a_2}\circ \cdots \circ {\delta }_{a_n}\right)\left(s_1\right)=s_2$. Thus, via the notion of the connected elements, a hypercomposition can be defined on $S$, as follows:

$$s_1+s_2=\{ \begin{array}{l}\left\{s\in S | s=s_{1}a \mathrm{and} s_2=sb, \mathrm{with} a,b\in E\right\}, \mathrm{if} s_2 \mathrm{is} \mathrm{connected} \mathrm{to} s_1\hfill \\ \left\{s_1, s_2\right\},\mathrm{if} s_2 \mathrm{is} \mathrm{not} \mathrm{connected} \mathrm{to} s_1\hfill \end{array}$$

Proposition 1.

If the set of the operators$E$over a non-void set$S$is a unitary magma, then$\left(S,+\right)$becomes a hypergroup.

Proof. 

Since $E$ is a unitary magma, the result of the hypercomposition always contains the two participating elements, thus $s+S=S+s=S$ for all $s\in S$ and so the reproductive axiom is valid. Moreover, the associativity holds. Indeed, if $s_1, s_2$ and $s_3$ are not connected to each other, then

$$s_1+\left(s_2+s_3\right)=\left(s_1+s_2\right)+s_3=\left\{s_1, s_2, s_3\right\}$$

Next, suppose that $s_2$ and $s_3$ are connected to $s_1$. Also let $s_3$ be connected to $s_2$. Then:

$$\begin{array}{ll}\left(s_1+s_2\right)+s_3\hfill & =\left\{q\in S | q=s_{1}a \mathrm{and} s_2=(s_{1}a)b, \mathrm{with} a,b\in E\right\}+s_3=\hfill \\ & =\left\{\begin{array}{l}s\in S | s=\left(s_{1}a\right)c, s_2=\left(s_{1}a\right)b, \mathrm{and}\hfill \\ s_3=\left(\left(s_{1}a\right)c\right)d \mathrm{with} a,b,c,d\in E\hfill \end{array}\right\}=\hfill \\ & =s_1+s_3\hfill \end{array}$$

and

$$\begin{array}{ll}{s}_1+\left(s_2+s_3\right)\hfill & =s_1+\left\{q\in S | q=s_{2}a \mathrm{and} s_3=(s_{2}a)b, \mathrm{with} a,b\in E\right\}=\hfill \\ & =\left\{\begin{array}{l}s\in S | s=s_{1}c \mathrm{and} \left(s_{1}c\right)d=s_{2}a, \left(s_{2}a\right)k=s_3 \mathrm{or} \\ \left(s_{1}c\right)l=s_3 \mathrm{with} a,c,d,k,l\in E\end{array}\right\}=\hfill \\ & =s_1+s_3\hfill \end{array}$$

Similar is the proof of all the other cases and hence the proposition. □

Corollary 1.

The set of vertices of a directed graph is endowed with the structure of the hypergroup if the result of the hypercomposition of two vertices v_i and v_j is the set of the vertices which appear in all the possible paths that connect v_i to v_j, or {v_i, v_j}, if there do not exist any connecting paths from vertex v_i to vertex v_j.

If $E$ is a magma, an equivalence relation $\xi$ on $E$ is called a congruence relation if

$$\left(a,b\right)\in \xi , \left(c,d\right)\in \xi \mathrm{implies} \{ \begin{array}{c} \left[\left\{y\right\}\times bd\right]\cap \xi \ne \varnothing \mathrm{for} \mathrm{all} y\in ac\\ \mathrm{and}\\ \left[ac\times \left\{z\right\}\right]\cap \xi \ne \varnothing \mathrm{for} \mathrm{all} z\in bd\end{array}$$

When the law of synthesis in the magma is a composition, then $ac$ and $bd$ are singletons and the above definition is simplified to:

$$\left(a,b\right)\in \xi , \left(c,d\right)\in \xi \mathrm{implies} \left(ac,bd\right)\in \xi$$

The set $\raisebox{1ex}{$E$}\!\left/ \!\raisebox{-1ex}{$\xi $}\right.$ of all equivalence classes defined on $E$ by $\xi$ becomes an associative magma if we define

$${\xi }_a·{\xi }_b=\left\{{\xi }_c | c\approx ab\right\} \mathrm{for} \mathrm{all} {\xi }_a,{\xi }_b\in \raisebox{1ex}{$E$}\!\left/ \!\raisebox{-1ex}{$\xi $}\right.$$

Proposition 2.

Every congruence relation$\xi$on a magma$E$is a normal equivalence relation, and therefore the set$\raisebox{1ex}{$E$}\!\left/ \!\raisebox{-1ex}{$\xi $}\right.$becomes a magma under the law of synthesis

$$C_x·C_y=\left\{C_z | z\approx xy\right\}$$

where$C_x$is the class of an arbitrary element$x\in E$.

Proof. 

Since $\xi$ is a congruence relation, for each $x,y\in E$ it holds:

$$\begin{array}{lll} z^{\prime }\in C_x·C_y& \Rightarrow & \\ & \Rightarrow & \left(\exists \left(x^{\prime },y^{\prime }\right)\right)\in C_x\times C_y) \left[z\approx x^{\prime }{y}^{\prime }\right]\Rightarrow \left(\exists z\approx xy\right)\left[z^{\prime }\xi z\right]\Rightarrow z^{\prime }\in C_z\Rightarrow \\ & \Rightarrow & C_x·C_y\subseteq {\displaystyle \underset{z\approx xy}{\cup }{C}_z}\end{array}$$

Conversely now:

$$\begin{array}{lll}{z}^{″}\in {\displaystyle \underset{z\approx xy}{\cup }{C}_z}& \Rightarrow & \\ & \Rightarrow & \left(\exists z\approx xy\right)\left[z^{″}\xi z\right]\Rightarrow \left(\exists \left(x^{″},y^{″}\right)\in E^2\right)\left[x^{″}\xi x\wedge y^{″}\xi y\wedge z^{″}\approx x^{″}{y}^{″}\right]\Rightarrow \\ & \Rightarrow & z^{″}\in C_x·C_y\Rightarrow {\displaystyle \underset{z\approx xy}{\cup }{C}_z}\subseteq C_x· C_y\end{array}$$

Thus, $C_x·C_y={\displaystyle \underset{z\approx xy}{\cup }{C}_z}$, and so the quotient set $\raisebox{1ex}{$E$}\!\left/ \!\raisebox{-1ex}{$\xi $}\right.$, enriched with the law of synthesis $C_x·C_y=\left\{C_z | z\approx xy\right\}$, is a magma. Obviously, if the law of synthesis is a composition, then the previous equality is simplified to $C_x·C_y=C_{xy}$. □

Corollary 2.

Every congruence relation$\xi$on a hypergroup$E$is a normal equivalence relation, and therefore the quotient$\raisebox{1ex}{$E$}\!\left/ \!\raisebox{-1ex}{$\xi $}\right.$becomes a hypergroup under the hypercomposition$C_x·C_y=\left\{C_z | z\approx xy\right\}$. If$E$is a group, then$\raisebox{1ex}{$E$}\!\left/ \!\raisebox{-1ex}{$\xi $}\right.$is a group as well, under the composition

$$C_x·C_y=C_{xy}$$

Proposition 3.

If$E$is a transposition magma and$\xi$is a congruence relation on$E$, then$\raisebox{1ex}{$E$}\!\left/ \!\raisebox{-1ex}{$\xi $}\right.$is a transposition magma.

Proof. 

Suppose that for some elements $C_x, C_y, C_z, C_w,$ of the quotient set $\raisebox{1ex}{$E$}\!\left/ \!\raisebox{-1ex}{$\xi $}\right.$ it holds that $C_y\backslash C_x\approx C_z/C_w$. Then there exist elements $x^{\prime }, y^{\prime }, z^{\prime }, w^{\prime }$ belonging to $C_x, C_y, C_z, C_w,$ respectively, such that $y^{\prime }\backslash x^{\prime }\approx z^{\prime }/w^{\prime }$. Since the transposition axiom is valid in $E$, it derives that $x^{\prime }{w}^{\prime }\approx y^{\prime }{z}^{\prime }$. Therefore, $C_x·C_w\approx C_y·C_z$ and hence the proposition. □

Definition 9.

A state machine M is a triplet$(S,E,\delta )$where$S$and$E$are sets and$\delta$is mapping of$S\times E$to$S$.

The set $S$ describes the internal qualities of the system. The elements of $S$ are called internal states of M. If $S$ is finite, then M is called a finite state machine. The set $E$ describes the environmental inputs that can affect the system. The mapping $\delta$ describes the environmental influences on the internal qualities of the system and it is called a state transition function. Such a system is obviously quite general and can be used in a variety of cases. From the mathematical standpoint, a state machine is a set with operators and the fact that we can successfully approach, describe and examine such systems via algebraic tools and techniques is one of the most impressive and remarkable achievements of modern algebra.

Example 1.

State machines can be depicted by the so-called transition diagrams. Thus, if $S=\left\{s_1\right\}$ and $E$ is a finite set, then the relevant state machine is illustrated with the transition diagram presented in Figure 1:

Moreover, if $S=\left\{s_1,s_2\right\}$ and $E=\left\{a\right\}$, we could have any of the following four state machines that are shown in Figure 2:

Another way of specifying a state machine is by writing out the transition function $\delta$ in tabular form, thus creating the so-called state transition table. For example, the state transition table of the last in the above figure state machine is the following one:

Suppose that $a\in E$ is applied to the state $s\in S$ of a state machine M. Then the machine moves to state $\delta \left(s,a\right)={\delta }_a\left(s\right)=sa$. Next, if another input, say $b\in E$, is applied to the machine, the resultant state is:

$$\delta \left({\delta }_a\left(s\right),b\right)={\delta }_b\left({\delta }_a\left(s\right)\right)={\delta }_b\left(sa\right)=\left(sa\right)b$$

Since ${\delta }_b\left({\delta }_a\left(s\right)\right)=\left({\delta }_b\circ {\delta }_a\right)\left(s\right)$, if $E$ is a magma, we say that the state transition function satisfies the associativity if ${\delta }_b\left({\delta }_a\left(s\right)\right)={\delta }_c\left(s\right), c\approx ab$. If the law of synthesis is a composition, then the associativity is of the form ${\delta }_b\left({\delta }_a\left(s\right)\right)={\delta }_{ab}\left(s\right)$ or equivalently $\left(sa\right)b=s\left(ab\right)$ and it is named mixed associativity, while if the law of synthesis is a hypercomposition, the associativity is fulfilled if $\left(sa\right)b\in s\left(ab\right)$ and it is called generalized mixed associativity [26,29,68].

Definition 10.

A state machine M = $(S,E,\delta )$ is called quasi-automaton if $E$ is a magma and the state transition function satisfies the mixed associativity, i.e., $\left(sa\right)b=s\left(ab\right)$ for any pair $a,b\in E$ and any state $s\in S$.

Definition 11.

A state machine M = (S,E,δ) is called quasi-multiautomaton if Ε is a magma and the state transition function satisfies the generalized mixed associativity, i.e., $\left(sa\right)b\in s\left(ab\right)$ for any pair $a,b\in E$ and any state $s\in S$.

A detailed presentation of the terminology, based on the historical development of the area, can be found in the well-written paper [29]. The above definitions are in line with [29]. Obviously, every quasi-automaton is a quasi-multiautomaton. Apparently, quasi-multiautomata which are not quasi-automata can only exist when E is a hypercompositional magma. On the contrary, quasi-automata exist when either the magma is endowed with a composition or when it is endowed with a hypercomposition. A special case of quasi-automata occurs when $E$ is a free semigroup or a free monoid instead of an arbitrary magma. In this case, computer theory tends to use the term “word” for the elements of $E$, the term “letter” for the elements of its generating set $\Sigma$ and the term concatenation of words for the law of synthesis in $E$. Moreover, the free semigroup generated by $\Sigma$ is denoted by ${\Sigma }^{+}$ and the corresponding free monoid by $\Sigma *$. Also, the quasi-automaton is denoted by M = (S,E,δ).

Proposition 4.

Let (S,E,δ) be a quasi-automaton and $\sim$ a binary relation on the magma, defined by

$$a\sim b\iff {\delta }_a={\delta }_b,\hspace{1em}where a,b\in E$$

Then $\sim$ is a congruence relation on $E$ and the magma $\raisebox{1ex}{$E$}\!\left/ \!\raisebox{-1ex}{$\sim $}\right.$ has the same algebraic structure as $E$.

Proof. 

This relation is easily seen to be an equivalence relation. Next, let $a\sim b$ and $c\sim d$. From $a\sim b$, it follows that ${\delta }_a\left(s\right)={\delta }_b\left(s\right)$ for all $s\in S$. Next, since $c\sim d$, the following sequence of equivalent statements holds:

$${\delta }_c\left({\delta }_a\left(s\right)\right)={\delta }_c\left({\delta }_b\left(s\right)\right); {\delta }_c\left({\delta }_a\left(s\right)\right)={\delta }_d\left({\delta }_b\left(s\right)\right); {\displaystyle \underset{y\approx ca}{\cup }{\delta }_y\left(s\right)}={\displaystyle \underset{z\approx db}{\cup }{\delta }_z\left(s\right)};$$

Therefore, $\sim$ is a congruence relation on $E$. Next, it is easy to see that the magma $\raisebox{1ex}{$E$}\!\left/ \!\raisebox{-1ex}{$\sim $}\right.$ is of the same type as $E$, that is, if $E$ is a semigroup, semi-hypergroup, hypergroup, group, etc., then $\raisebox{1ex}{$E$}\!\left/ \!\raisebox{-1ex}{$\sim $}\right.$ has the same algebraic structure, respectively. □

Now, if M = (S,E,δ) is a quasi-automaton, then the semigroup $E=\raisebox{1ex}{${\Sigma }^{+}$}\!\left/ \!\raisebox{-1ex}{$\sim $}\right.$ or the monoid $E=\raisebox{1ex}{$\Sigma *$}\!\left/ \!\raisebox{-1ex}{$\sim $}\right.$ can be constructed with the use of Proposition 4. In many cases, it is more convenient to study this semigroup rather than the original machine M. However, if we do not want to lose sight of the set of states, we consider the machine M = (S,E,δ). Each element of $E$ is an equivalence class of ${\Sigma }^{+}$ or $\Sigma *$, which acts on $S$ as follows: $s\left[a\right]={\delta }_a\left(s\right)$, where $s\in S$ and $a\in {\Sigma }^{+}$ or $a\in \Sigma *$.

4. The Magma of 2 Elements

In this section, we will proceed to a detailed study and classification of the two-element magma, which is the binary state machines’ environment.

While there exists only one single element magma which is a group and also a LA/RA-group, there exist 3⁴ = 81 magmas with 2 elements. These magmas can be constructed, classified and enumerated, with the techniques and methods which are developed in [69,70,71] and [63]. In the following propositions, these magmas are presented via their Cayley tables. Note that, in a Cayley table, the entry in the row headed by x and the column headed by y is the synthesis x⋅y.

i. 

Associative Magmas

Proposition 5.

There exist 6 semigroups which are classified into 2 classes with 2 isomorphic semigroups each, and into 2 single-member classes, which are presented below via their Cayley tables. Moreover, since SG₁and SG₂are commutative, they satisfy both the left and the right inverted associativity.

Remark 1.

When $a=0$ and $b=1$ in the two isomorphic semigroups SG₂, we get the two well-known operations of the Boolean algebra:

Proposition 6.

There exist 10 semihypergroups which are classified into 5 classes with 2 isomorphic semihypergroups each. These are displayed below in the form of Cayley tables. Moreover, since $S{H}_1$ is commutative, it satisfies both the left and the right inverted associativity.

ii. 

Reproductive Magmas

Proposition 7.

There exist 21 quasihypergroups which are classified into 9 two-member classes and 3 single-member classes, which are presented below via their Cayley tables.

iii. 

Associative and Reproductive Magmas

Proposition 8.

There exists one class with 2 isomorphic commutative groups.

Proposition 9.

There exist 12 hypergroups which are classified into 5 classes with 2 isomorphic hypergroups each and into 2 single-member classes, which are presented below via their Cayley tables.$H_3-H_7$are commutative.

$H_6$ is the two-element B-hypergroup. B(inary)-hypergroups came into being during the study of formal languages and automata with the use of hypercompositional algebra [5,13,16,17]. The free monoid of the words generated by an alphabet Σ can be endowed with the B-hypergroup structure, and so become a join hyperringoid [21,72,73,74], which is named linguistic hyperringoid [14,21,73,74]. If the B-hypergroup is fortified with a strong identity [31], which is necessary for the theory of formal languages and automata [14,21], then the join hyperring comes into being [72,73,74]. $H_7$ is the two-element total hypergroup.

Proposition 10.

All the two-element hypergroups are transposition hypergroups.

Proof. 

The Cayley tables of the induced hypercompositions for the seven two-element hypergroups are presented below. For the classes with two elements, we chose the first hypergroup for the presentation of the induced hypercomposition. Observe that the hypergroups $H_3, H_4, H_5, H_6$ and $H_7$ are commutative; therefore, the two induced hypercompositions coincide, and so there is only one Cayley table corresponding to each one of them. As mentioned above, in the Cayley tables, the entry in the row headed by x and the column headed by y is the synthesis x/y or y\x respectively.

The verification of the transposition axiom gives the rest. □

So, according to Proposition 10, there do not exist non-transposition hypergroups with cardinality 1 or 2. However, as shown in the following example, there exist non-transposition hypergroups if their cardinality is greater than or equal to 3.

Example 2.

The hypercomposition on hypergroup H₆ can be written in the following two ways:

$$a·b=\{ \begin{array}{l}\left\{a,b\right\}, if a\ne b\hfill \\ a, \hspace{1em}if a=b\hfill \end{array}$$

(1)

and

$$a·b=\{ \begin{array}{c}H, if a\ne b\\ a, if a=b\end{array}$$

(2)

If$H=\left\{a,b\right\}$, then the above two formulas give the same hypercomposition, but if cardH ≥ 3, then they produce two different hypergroups. The first one, which is the B-hypergroup, satisfies the transposition axiom (see [13] for the proof), while the second one does not. Indeed, the induced hypercomposition of (2) is:

$$a·b=\{ \begin{array}{l}H··\left\{b\right\}, if a\ne b\hfill \\ a, \hspace{1em}\hspace{1em} if a=b\hfill \end{array}$$

Next, if$a\ne b$, we have:

$$a/b\cap b/a=\left[H··\left\{b\right\}\right]\cap \left[H··\left\{a\right\}\right]\ne \varnothing$$

while

$$aa\cap bb=\left\{a\right\}\cap \left\{b\right\}=\varnothing .$$

Moreover, the verification of the reverse transposition axiom for hypergroups $H_1-H_7$ leads to the following result:

Proposition 11.

All the two-element hypergroups satisfy the strong reverse transposition axiom.

A consequence of Propositions 10 and 11 is the following Theorem:

Theorem 3.

All the two-element hypergroups satisfy the bilateral transposition axiom.

In [9], following the observation that the quasicanonical hypergroups, the canonical hypergroups, and of course, the groups and the abelian groups satisfy the bilateral transposition axiom, the question arose: Do there exist other hypergroups satisfying the bilateral transposition axiom apart from the quasicanonical and the canonical ones? The above Theorem 3 gives the affirmative answer to this question.

iv. 

Magmas with inverted associativity

Proposition 12.

There exists only one class with 2 isomorphic left almost-semihypergroups, as per the following Cayley tables.

Proposition 13.

In addition to the five non-isomorphic commutative hypergroups (and hence left and right almost-hypergroups) that are mentioned in Proposition 9, there also exist two non-isomorphic left almost-hypergroups which are classified into one two-member class and into one single-member class, as per the following Cayley tables.

Proposition 14.

There exists only one class with 2 isomorphic right almost-semihypergroups, as per the following Cayley tables.

Proposition 15.

In addition to the five non-isomorphic commutative hypergroups (and hence left and right almost-hypergroups) that are mentioned in Proposition 9, there also exist two non-isomorphic right almost-hypergroups which are classified into one two-member class and into one single-member class, as they are presented in the following Cayley tables.

v. 

Rigid Magmas

The remaining 26 magmas are classified into 12 two-member classes and into two single-member classes. The law of synthesis on the 2 magmas of the single-member classes is a composition. The same goes for the magmas in three of the twelve two-member classes.

Proposition 16.

There exist only two non-isomorphic groupoids of two elements, which are presented in the following Cayley tables.

Definition 12.

A magma is called rigid if its group of automorphisms is of order 1.

As it is shown in [75,76], there exist 21 rigid hypergroupoids whose classification is described in Theorem 4 of [76]. The following Theorem 4 applies to the two-element magmas:

Theorem 4.

There exist 9 rigid magmas of two elements, classified as follows:

i. 

2 non-commutative groupoids, which do not satisfy the transposition axiom;

ii. 

2 non-commutative transposition semigroups;

iii. 

1 commutative quasi-hypergroup, which does not satisfy the transposition axiom;

iv. 

1 LA-hypergroup, which does not satisfy the transposition axiom;

v. 

1 RA-hypergroup, which does not satisfy the transposition axiom;

vi. 

2 hypergroups, which satisfy both the left and right invert associativity.

Proof. 

i. 

Let us consider the first groupoid of Proposition 15. Then, the two induced hypercompositions are given in the following Cayley tables:

Next, we have that $a/b\cap b\backslash a=\left\{a,b\right\}\cap \left\{b\right\}\ne \varnothing$, while $ab\cap ba=\left\{a\right\}\cap \left\{b\right\}=\varnothing$. Therefore, the transposition axiom is not valid. Analogous is the proof for the second groupoid.

ii. 

Let us consider the semigroup SG₃. Then, the two induced hypercompositions are the following ones:

The verification of the transposition axiom, according to the above Cayley tables, proves its validity. The same goes for the case of SG₄.

iii. 

Since QH₁₀ is commutative, the two induced hypercompositions coincide and so we have:

$$a/b=b/a=\left\{a,b\right\},\hspace{1em}\hspace{1em}a/a=b,\hspace{1em}\hspace{1em}b/b=a$$

Next, $a/b\cap b/a=\left\{a,b\right\}\ne \varnothing$ but $aa\cap bb=\varnothing$. Therefore, the transposition axiom is not valid.

iv. 

The induced hypercompositions on the LA-H₂ are:

Since the implication

$$b/a\cap a\backslash b=\left\{a\right\}\cap \left\{a,b\right\}\ne \varnothing \Rightarrow ab\cap ba=\varnothing$$

holds, the transposition axiom is not valid.

v. 

It is true as it is the dual of iv.

vi. 

The two hypergroups are H₆ and H₇. H₆ is a B-hypergroup. As it is well known, the B-hypergroups are join hypergroups (see [13] for the proof), that is, commutative hypergroups which satisfy the transposition axiom. H₇ is the two-element total hypergroup and total hypergroups are join hypergroups as well [5,9,13]. □

5. Binary State Machines

Let M = (S,E,δ) be a state machine. Two states, $s, t$, are called connected if there exists a sequence of inputs which causes $S$ to leave state $s$ and go into state $t$, that is, if there exists a sequence $a_1,a_2,\dots ,a_n$ of elements of $E$ such that $\left({\delta }_{a_1}\circ {\delta }_{a_2}\circ \cdots \circ {\delta }_{a_n}\right)\left(s\right)=t$. The states $s, t$ are called isolated to each other if neither $s$ is connected to $t$, nor $t$ to $s$. A state machine M is called connected if its undirected graph is connected, while it is called strongly connected if every ordered pair $\left(s,t\right)$ of states in $S$ is connected.

Proposition 17.

Suppose that the connected state machine M = (S,E,δ) is a quasi-multiautomaton. Then, for every pair $\left(s,t\right)$ of states, there exists one element of E which connects them, i.e., ${\delta }_a\left(s\right)=t$ for some $a\in E$.

Proof. 

Let $a_1,a_2,\dots ,a_n$ be a sequence of elements of $E$ such that $\left({\delta }_{a_1}\circ {\delta }_{a_2}\circ \cdots \circ {\delta }_{a_n}\right)\left(s\right)=t$. If $n=1$ the proposition is obvious. Let $n>1$. Then

$$\begin{array}{l}\left({\delta }_{a_1}\circ {\delta }_{a_2}\circ \cdots \circ {\delta }_{a_n}\right)\left(s\right)={\delta }_{a_1}\left({\delta }_{a_2}\left(\cdots {\delta }_{a_{n-1}}\left({\delta }_{a_n}\left(s\right)\right)\right)\right)\in \\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em} \in {\displaystyle \underset{a\in a_1{a}_2\dots a_n}{\cup }{\delta }_a\left(s\right)=\left\{\delta \left(s,a\right) | a\in a_1{a}_2\dots a_n\right\}}\end{array}$$

Hence, there exists $a\in a_1{a}_2\dots a_n$ such that $t=\delta (s,a)$. □

Theorem 5.

If the magma$E$in a quasi-multiautomaton M = (S,E,δ) has n elements, then the set $S$ cannot have more than n + 1 states.

Proof. 

As per Proposition 17, for every pair of states $\left(s,t\right)$, there exists one element of E which connects them, i.e., there exists $a\in E$ such that $\delta \left(s,a\right)=t$. Therefore, if $cardE=n$ e.g., if $E=\left\{a_1,a_2,\dots ,a_n\right\}$, then, for each state $s\in S$, there exist at most $n$ states connected with $s$, which are the $s_i=\delta \left(s,a_i\right), 1\le i\le n$. Next, if some state $s_k\in S$ yields $\delta \left(s_k,a_j\right)=t$, then, since $s_k=\delta \left(s,a_k\right)$, it holds that

$$t=\delta \left(\delta \left(s,a_k\right),a_j\right)\in \left\{\delta \left(s,a\right) | a\in a_k{a}_j\right\}\subseteq S$$

Hence, $S=\left\{s,s_1,s_2,\dots ,s_n\right\}$ and so the Theorem. □

Definition 13.

If the magma$E$of a state machine M = (S,E,δ) has 2 elements, then M is called a binary state machine.

Corollary 3.

The set$S$of the states of a binary quasi-multiautomaton M = (S,E,δ) cannot have more than 3 elements.

Theorem 6.

There exists 1 binary state machine with 1 state, 16 binary state machines with 2 states and 729 with 3 states.

Proof. 

The state transition table of a state machine with 1 state is:

The state transition table of a state machine with 2 states is:

where $x,y,z,w\in \left\{s_1,s_2\right\}$. Hence, there exist 2⁴ = 16 different to each other binary state machines with 2 states.

Moreover, the state transition table of the state machines with 3 states is:

where $x,y,z,w,u,v\in \left\{s_1,s_2,s_3\right\}$. Therefore, there are 3⁶ = 729 different to each other binary state machines with three states. □

Definition 14.

Two state machines M₁ = (S₁,E₁,δ₁) and M₂ = (S₂,E₂,δ₂) are isomorphic if E₁ and E₂ are isomorphic and there exists a one-to-one mapping f from S₁ onto S₂ such that

$f\left({\delta }_1\left(s,a\right)\right)={\delta }_2\left(f\left(s\right),a\right)$.

Theorem 7.

There exist 10 isomorphic binary state machines with 2 states, which are classified into 6 two-element classes and into 4 single-element classes, as presented in Figure 3:

Next, we will find which state machines are quasi-multiautomata or quasi-automata when their magma is a group or a hypergroup. In the proofs of the following propositions, we use the first member of each state machine class as the representative of the entire class. Similarly, the representative of every class from the group or the hypergroups will be its first member.

Proposition 18. 

If E is the group G₁(Proposition 8), then the state machines SM₄, SM₉, SM₁₀are quasi-automata.

Proof. 

The verification of the axioms shows that SM₄, SM₉, SM₁₀ are quasi-automata. The rest state machines do not satisfy the mixed associativity. Indeed:

• For SM₁ it holds: $\left(s_{2}a\right)b=s_{1}b=s_2$ while $s_2\left(ab\right)=s_{2}b=s_1$.
• For SM₂ it holds: $\left(s_{1}b\right)b=s_{1}b=s_1$ while $s_1\left(bb\right)=s_{1}a=s_2$.
• For SM₃ it holds: $\left(s_{2}b\right)a=s_{1}a=s_2$ while $s_2\left(ba\right)=s_{2}b=s_1$.
• For SM₅ it holds: $\left(s_{2}a\right)b=s_{1}b=s_1$ while $s_2\left(ab\right)=s_{2}b=s_2$.
• For SM₆ it holds: $\left(s_{2}b\right)b=s_{1}b=s_1$ while $s_2\left(bb\right)=s_{2}a=s_2$.
• For SM₇ it holds: $\left(s_{1}a\right)a=s_{2}a=s_1$ while $s_1\left(aa\right)=s_{1}a=s_2$.
• For SM₈ it holds: $\left(s_{1}b\right)a=s_{1}a=s_2$ while $s_1\left(ba\right)=s_{1}b=s_1$. □

Proposition 19.

If E is the hypergroup H₁(Proposition 9), then the state machines SM₃, SM₆, SM₉are quasi-multiautomata and the state machines SM₄, SM₁₀are quasi-automata.

Proof. 

The state machines SM₃, SM₆, SM₉ satisfy the generalized mixed associativity and hence they are quasi-multiautomata. Indicatively, for SM₃ we have:

$$\left(s_{1}b\right)a=s_{1}a=s_2 \mathrm{and} s_1\left(ba\right)=s_1\left\{a,b\right\}=\left\{s_{1}a, s_{1}b\right\}=\left\{s_2, s_1\right\}, \mathrm{thus} \left(s_{1}b\right)a\in s_1\left(ba\right)$$

The state machines SM₄ and SM₁₀ satisfy the mixed associativity and so they are quasi-automata. Indicatively, for SM₄ we have:

$$\left(s_{2}b\right)a=s_{1}a=s_1 \mathrm{and} s_2\left(ba\right)=s_2\left\{a,b\right\}=\left\{s_{2}a, s_{2}b\right\}=s_1, \mathrm{thus} \left(s_{2}b\right)a=s_2\left(ba\right)$$

The rest state machines do not satisfy any associativity condition. Indeed:

• For SM₁ it holds: $\left(s_{2}a\right)b=s_{1}b=s_2$ while $s_2\left(ab\right)=s_{2}b=s_1$.
• For SM₂ it holds: $\left(s_{2}a\right)a=s_{1}a=s_2$ while $s_2\left(aa\right)=s_{2}a=s_1$.
• For SM₅ it holds: $\left(s_{2}a\right)b=s_{1}b=s_1$ while $s_2\left(ab\right)=s_{2}b=s_2$.
• For SM₇ it holds: $\left(s_{1}a\right)a=s_{2}a=s_1$ while $s_1\left(aa\right)=s_{1}a=s_2$.
• For SM₈ it holds: $\left(s_{1}a\right)b=s_{2}b=s_2$ while $s_1\left(ab\right)=s_{1}b=s_1$. □

Proposition 20.

If E is the hypergroup H₂(Proposition 9), then the state machines SM₆, SM₉are quasi-multiautomata and the state machines SM₄, SM₁₀are quasi-automata.

Proof. 

The state machines SM₆, SM₉ satisfy the generalized mixed associativity, and therefore they are quasi-multiautomata, while SM₄ and SM₁₀ satisfy the mixed associativity and so they are quasi-automata. The rest state machines do not satisfy any associativity condition. Indeed:

• For SM₁ it holds: $\left(s_{2}a\right)b=s_{1}b=s_2$ while $s_2\left(ab\right)=s_2\left\{a,b\right\}=\left\{s_{2}a,s_{2}b\right\}=s_1$.
• For SM₂ it holds: $\left(s_{2}a\right)a=s_{1}a=s_2$ while $s_2\left(aa\right)=s_{2}a=s_1$.
• For SM₃ it holds: $\left(s_{2}b\right)a=s_{1}a=s_2$ while $s_2\left(ba\right)=s_{2}b=s_1$.
• For SM₅ it holds: $\left(s_{2}b\right)a=s_{2}a=s_1$ while $s_2\left(ba\right)=s_{2}b=s_2$.
• For SM₇ it holds: $\left(s_{1}a\right)a=s_{2}a=s_1$ while $s_1\left(aa\right)=s_{1}a=s_2$.
• For SM₈ it holds: $\left(s_{1}a\right)a=s_{2}a=s_1$ while $s_1\left(aa\right)=s_{1}a=s_2$. □

Proposition 21.

If E is the hypergroup H₃(Proposition 9), then the state machines SM₆, SM₉are quasi-multiautomata and the state machines SM₄, SM₁₀are quasi-automata.

Proof. 

The state machines SM₆, SM₉ satisfy the generalized mixed associativity, and therefore they are quasi-multiautomata, while SM₄ and SM₁₀ satisfy the mixed associativity and therefore they are quasi-automata. The rest state machines do not satisfy any associativity condition. Indeed:

• For SM₁ it holds: $\left(s_{2}a\right)b=s_{1}b=s_2$ while $s_2\left(ab\right)=s_{2}b=s_1$.
• For SM₂ it holds: $\left(s_{2}a\right)a=s_{1}a=s_2$ while $s_2\left(aa\right)=s_{2}a=s_1$.
• For SM₃ it holds: $\left(s_{2}b\right)a=s_{1}a=s_2$ while $s_2\left(ba\right)=s_{2}b=s_1$.
• For SM₅ it holds: $\left(s_{2}a\right)b=s_{1}b=s_1$ while $s_2\left(ab\right)=s_{2}b=s_2$.
• For SM₇ it holds: $\left(s_{1}a\right)a=s_{2}a=s_1$ while $s_1\left(aa\right)=s_{1}a=s_2$.
• For SM₈ it holds: $\left(s_{1}b\right)a=s_{1}a=s_2$ while $s_1\left(ba\right)=s_{1}b=s_1$. □

Proposition 22.

If E is the hypergroup H₄(Proposition 9), then the state machines SM₃, SM₅, SM₆, SM₉are quasi-multiautomata and the state machines SM₄, SM₁₀are quasi-automata.

Proof. 

The state machines SM₃, SM₅, SM₆, SM₉ satisfy the generalized mixed associativity, and therefore they are quasi-multiautomata, while SM₄ and SM₁₀ satisfy the mixed associativity and therefore they are quasi-automata. The rest state machines do not satisfy any associativity condition. Indeed:

• For SM₁ it holds: $\left(s_{2}a\right)b=s_{1}b=s_2$ while $s_2\left(ab\right)=s_2\left\{a,b\right\}=\left\{s_{2}a,s_{2}b\right\}=s_1$.
• For SM₂ it holds: $\left(s_{1}a\right)a=s_{2}a=s_1$ while $s_1\left(aa\right)=s_{1}a=s_2$.
• For SM₇ it holds: $\left(s_{1}a\right)b=s_{2}b=s_1$ while $s_1\left(ab\right)=s_1\left\{a,b\right\}=\left\{s_{1}a, s_{1}b\right\}=s_2$.
• For SM₈ it holds: $\left(s_{1}a\right)a=s_{2}a=s_1$ while $s_1\left(aa\right)=s_{1}a=s_2$. □

Proposition 23.

If E is the hypergroup H₅(Proposition 9), then the state machine SM₈is a quasi-multiautomaton and the state machines SM₄, SM₁₀are quasi-automata.

Proof. 

The state machine SM₈ satisfies the generalized mixed associativity, and therefore it is a quasi-multiautomaton, while SM₄ and SM₁₀ satisfy the mixed associativity and therefore they are quasi-automata. The rest state machines do not satisfy any associativity condition. Indeed:

• For SM₁ it holds: $\left(s_{1}a\right)a=s_{1}a=s_1$ while $s_1\left(aa\right)=s_{1}b=s_2$.
• For SM₂ it holds: $\left(s_{2}a\right)a=s_{1}a=s_2$ while $s_2\left(aa\right)=s_{2}b=s_1$.
• For SM₃ it holds: $\left(s_{1}a\right)a=s_{2}a=s_2$ while $s_1\left(aa\right)=s_{1}b=s_1$.
• For SM₅ it holds: $\left(s_{2}a\right)a=s_{1}a=s_1$ while $s_2\left(aa\right)=s_{2}b=s_2$.
• For SM₆ it holds: $\left(s_{2}a\right)a=s_{2}a=s_2$ while $s_2\left(aa\right)=s_{2}b=s_1$.
• For SM₇ it holds: $\left(s_{1}a\right)a=s_{2}a=s_1$ while $s_1\left(aa\right)=s_{1}b=s_2$.
• For SM₉ it holds: $\left(s_{1}a\right)a=s_{1}a=s_1$ while $s_1\left(aa\right)=s_{1}b=s_2$. □

Proposition 24.

If E is the hypergroup H₆(Proposition 9), then the state machines SM₃, SM₅, SM₆are quasi-multiautomata and the state machines SM₄, SM₁₀are quasi-automata.

Proof. 

The state machines SM₃, SM₅, SM₆ satisfy the generalized mixed associativity, and therefore they are quasi-multiautomata, while SM₄ and SM₁₀ satisfy the mixed associativity and therefore they are quasi-automata. For the rest state machines, observe that they satisfy none of the associativity conditions. Indeed:

• For SM₁ it holds: $\left(s_{2}b\right)b=s_{1}b=s_2$ while $s_2\left(bb\right)=s_{2}b=s_1$.
• For SM₂ it holds: $\left(s_{2}a\right)a=s_{1}a=s_2$ while $s_2\left(aa\right)=s_{2}a=s_1$.
• For SM₇ it holds: $\left(s_{1}a\right)a=s_{2}a=s_1$ while $s_1\left(aa\right)=s_{1}a=s_2$.
• For SM₈ it holds: $\left(s_{1}a\right)a=s_{2}a=s_1$ while $s_1\left(aa\right)=s_{1}a=s_2$.
• For SM₉ it holds: $\left(s_{1}b\right)b=s_{1}b=s_2$ while $s_2\left(bb\right)=s_{2}b=s_1$. □

Proposition 25.

If E is the hypergroup H₇(Proposition 9), then the state machines SM₃, SM₅, SM₆, SM₈, SM₉are quasi-multiautomata and the state machines SM₄, SM₁₀are quasi-automata.

Proof. 

The state machines SM₃, SM₅, SM₆, SM₈, SM₉ satisfy the generalized mixed associativity, and therefore they are quasi-multiautomata, while SM₄ and SM₁₀ satisfy the mixed associativity and therefore they are quasi-automata. The remaining state machines satisfy none of the associativity conditions. Indeed:

• For SM₁ it holds: $\left(s_{2}a\right)b=s_{1}b=s_2$ while $s_2\left(ab\right)=s_2\left\{a,b\right\}=\left\{s_{2}a,s_{2}b\right\}=s_1$.
• For SM₂ it holds: $\left(s_{2}a\right)a=s_{1}a=s_2$ while $s_2\left(aa\right)=s_2\left\{a,b\right\}=\left\{s_{2}a, s_{2}b\right\}=s_1$.
• For SM₇ it holds: $\left(s_{2}a\right)a=s_{1}a=s_2$ while $s_1\left(aa\right)=s_2\left\{a,b\right\}=\left\{s_{2}a, s_{2}b\right\}=s_1$. □

6. Conclusions and Open Problems

This paper approaches the state machines from within their environment in which they can “survive”, i.e., exist and operate. They are given an extended definition which derives from the consideration that the environment in which they can exist is an algebraic magma in the sense of [9], where the initial definition of magma by N. Bourbaki [8] is generalized for the purpose of incorporating algebraic structures endowed with hypercompositional laws. Hence, a state machine M is defined as a triplet (S,E,δ), where S is the set of the states of the machine, E is the set of the environmental inputs to the machine and δ is a mapping of S × E to S, which describes the interaction between each state and its environment. Our study focuses on the binary state machines, where E is a two-element magma and our results can be summarized in

Table 1. Classification of the magmas with two elements.

	Total Number	Isomorphism Classes	Classes with 1 Member (Rigid)	Classes with 2 Members
binary magmas	81	45	9	36
binary magmas with composition	16	10	4	6
binary magmas with hypercomposition	65	35	5	30
non-reproductive semigroups	6	4	2	2
non-reproductive semihypergroups	10	5		5
non-reproductive LA-semihypergroups	2	1		1
non-reproductive RA-semihypergroups	2	1		1
non-associative quasihypergroups	21	11	3	9
groups	2	1		1
hypergroups/transposition hypergroups	12	7	2	5
LA-hypergroups	3	2	1	1
RA-hypergroups	3	2	1	1

:

With regard to the classification given in this table, we note that according to the above Theorem 3, the two-element hypergroups are not just transposition hypergroups (row 10), but bilateral transposition hypergroups. Hence, the hitherto open question which was asked in [9] is answered affirmatively.

Of all the structures that appear in the above table, this paper presents the state machines with two states whose environment is a two-element group or two-element hypergroups. The results are presented in

Table 2. Binary state machines with two states.

Group/Hypergroup	Non-Isomorphic Quasiautomata	Non-Isomorphic Quasi-Multiautomata
$G_1$	3
$H_1$	2	3
$H_2$	2	2
$H_3$	2	2
$H_4$	2	4
$H_5$	2	1
$H_6$	2	3
$H_7$	2	5

:

According to Corollary 3, only quasiautomata and quasi-multiautomata with up to three states can operate in the environment of a two-element magma. The description of the three state binary machines, as well as the investigation of the state machines which correspond to algebraic structures of $E$ that are other than groups or hypergroups, still remain open problems. This question becomes more complicated in the instances when $E$ is enriched with two laws of synthesis, as it happens in a hyperringoid [74]. It is worth mentioning here that $E$ is a hyperringoid in specific state machines like the automata, where the environment is defined via an alphabet [16,17,21].

All of the above refer to deterministic state machines. However, the state transition function can be a mapping from $S\times E$ to the power set $P\left(S\right)$ of $S$, defining thus the non-deterministic state machines (see also [13,14,67]). This consideration broadens the margins of the study as there can exist state transition functions for which $\delta \left(s,a\right)$ is not necessarily just a single element. It can be more than one element and it can also be none, as it is possible for $\delta \left(s,a\right)$ to be equal to the empty set.