{%hackmd @RintarouTW/About %}

# Monoid and Automata

## Monoid

:::info
A Monoid is a set $M$ with a binary operation $\cdot$ with the properties:
- $\cdot$ is associative : $\forall a,b,c \in M, a(bc)=(ab)c$
- $\cdot$ has an identity : $\forall a\in M,\exists e\in M, ae=ea=a$
:::

ex:

$$
[\mathcal{P}(A);\cup]\\
[\mathcal{P}(A);\cap]\\
[\mathcal{P}(A);\oplus]\\
[Z_n;+_n]\\
[M_n(\mathbb{Z});\cdot]\\
[X^X;\circ(function\ composition)]
$$

### Submonoid

:::info
$$
\cases{
[M;\cdot]\ is\ a\ monoid\\
[K;\cdot]\ is\ a\ submonoid\ of\ M
}\iff
\cases{
K\subseteq M\\
\forall a,b\in K, ab\in K\iff K\ is\ closed\ under\ \cdot\\
\exists! e\in M\implies e\in K
}
$$
:::

### Submonoid Generated by a Set = $\langle S\rangle$

:::info
$[M;\cdot]$ is a monoid and $S\subset M$
$\langle S\rangle$ is a submonoid of $M$ $\iff \cases{e\in M\implies e\in \langle S\rangle\\\forall a\in S, a\in\langle S\rangle\\\forall a,b\in \langle S\rangle, ab\in\langle S\rangle}$
:::

ex:

$\langle 2\rangle = \{0,2,4,6,8,\ldots\}$ is a submonoid of $[\mathbb{Z};+]$

$S=\{\{1\},\{2\},\{3\}\},\langle S\rangle=\mathcal{P}(\{1,2,3\})$ is a submonoid of $[\mathcal{P}(\mathbb{Z});\cup]$ with ideneity $\varnothing$.

:::info
Stochastic Matrix
An $n\times n$ matrix of real numbers is called **stochastic** if each entry is nonnegative and the sum of entries in each column is 1.

$$A,B\in M_n(\mathbb{R})\ are\ both\ stochastic.
\implies\cases{1\le i,j\le n\\
\sum_\limits{i=1}^n a_{ij} =1\\
\sum_\limits{i=1}^n b_{ij} =1\\
}\\
\therefore (AB)_{ij} = \sum_\limits{k=1}^n a_{ik}b_{kj}\\
\begin{array}l
\implies Sum\ of\ j-th\ column\ of\ AB&=\sum_\limits{i=1}^n (AB)_{ij}\\
&=\sum_\limits{k=1}^n a_{1k}b_{kj} + \sum_\limits{k=1}^n a_{2k}b_{kj} + \cdots + \sum_\limits{k=1}^n a_{nk}b_{kj}\\
&= \sum_\limits{k=1}^n (a_{1k}+a_{2k}+\cdots+a_{nk})b_{kj}\\
&= \sum_\limits{k=1}^n b_{kj}\\
&= 1
\end{array}
$$
:::

## Free Monoids and Languages

:::info
Strings over an Alphabet
$A^n = a_1a_2\ldots a_n$ : A string of length $n, n \ge 1$ over alphabet A.
$\lambda:$ The null string. $A^0 = \{\lambda\}$
$A^*$ : The set of all strings over $A$.
If the length of string $s$ is $n$, we write $|s| = n$.
$A^*=A^0\cup A^1\cup A^2\cdots$, if $i\ne j, A^i\cap A^j=\varnothing$, $\{A^0,A^1,A^2,\ldots\}$ is a partition of $A^*$.
:::

if $A$ is **countable**, then $A^*$ is **countable**.

### Concatenation

:::info
$$
\cases{
a=a_1a_2\ldots a_m, |a|=m\\
b=b_1b_2\ldots b_n, |b|=n\\
}\implies
\cases{
a+b=a_1a_2\ldots a_mb_1b_2\ldots b_n\\
|a+b|=m+n
}
$$

$$
[A^*; +]\text{ is a monoid} \iff\cases{
\forall a,b,c\in A^*, a+(b+c)=(a+b)+c\\
e = \lambda, \forall a\in A^*, ae=ea=a
}
$$

$$
|A_1|=|A_2|\implies A_1^*\ and\ A_2^*\ are\ isomorphic.\\
\Updownarrow\\
\exists f:A_1\to A_2, f\text{ is a bijection.}
$$
:::

### Formal Language

:::info
If $A$ is an alphabet, a formal language over $A$ is a subset of $A^*$
:::

### Phrase Structure Grammar

:::info
1. terminal characters: $t\in A$
2. nonterminal characters: $N$
3. start symbol : $S\in N$
4. a finite set of production rules : $X,Y\in A\cup N, X\to Y, X\ne Y, X$ contains at least one nonterminal characters.
:::

If $G$ is a phrase structure grammar, $L(G)$ is the set of strings that can be produced by starting with $S$ and applying the production rules a finite number of times until no nonterminal characters remain.

If a language can be defined by a phrase structure grammar, then it is called a **phrase structure language**.

### Backus-Naur Form

:::info
$$
\cases{
A\to B_1, A\to B_2,\ldots, A\to B_n\iff A ::= B_1|B_2|\cdots|B_n\\
\{x\}\iff\text{zero and more repetition}\\
[y]\iff y \text{ is optional}
}
$$

ex:

$$
\cases{
letter ::= a | b | c | · · · | z | A | B | · · · | Z \\
digit ::= 0 | 1 | · · · | 9\\
I ::= letter\{letter | digit | \_\}
}
$$
:::

### Regular Grammar

:::info
$$
\cases{
t: terminal\\
right-hand-form : A\to t|A\to Bt\\
left-hand-form : A\to t|A\to tB\\
}
$$
:::

## Automata, Finite-State Machines

### Finite-State Machine

:::info
$$
Finite-State\ Machine=(S,X,Z,w,t)\\
\cases{
S:\{s_1,s_2,\ldots,s_r\}, state\\
X:\{x_1,x_2,\ldots,x_m\}, input\ alphabet\\
Z:\{z_1,z_2,\ldots,z_n\}, output\ alphabet\\
w:X\times S\to Z,\text{ the output/write function}\iff z=w(x,s)\in Z\\
t:X\times S\to S,\text{ the (state) transition function}\iff s'=t(x,s)\in S\\
}
$$
:::

:::info
Gray Code Decoder

digraph {
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800";fontcolor="#aaaaaa"];
rankdir=LR;
Copy->Complement [xlabel="1/1"];
Copy->Copy [label="0/0"];
Complement->Copy [xlabel="1/0"];
Complement->Complement [label="0/1"];
}

:::

## The Monoid of a Finite-State Machine

:::info
Every finite-state machine has a monoid associated with it.
:::

For any finite-state machine, the elements of its associated monoid **correspond to certain input sequences**. Because only **a finite number of combinations of states($s$) and inputs($x$)** is possible for a finite-state machine there is only **a finite number of input sequences that summarize the machine**.

:::info
$$
\cases{
S: set\ of\ states\\
X: set\ of\ inputs\\
Z: set\ of\ outputs
}\\
t: S\times X\to S\times Z\\
$$

$$
\cases{
s_{in}, s_{out} \in S\\
x\in X\\
z\in Z
}\implies t(s_{in},x)=(s_{out}, z)
$$

$s_{out}$ would be the $s_{in}$ of the next input.

All the possible combination of $s_{in}$ and $s_{out}$ are exactly $S$, the mapping/state transition could be denoted as a function of $T(x)$ or $T_{x}$.
:::

### Parity Checker

digraph {
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800";fontcolor="#aaaaaa"];
rankdir=LR;
Even->Even[xlabel="0/0"];
Even->Odd[xlabel="1/1"];
Odd->Even[label="1/0"];
Odd->Odd[label="0/1"];
}

$$
\begin{array}{lcccccc}
\text{Input}(x) & 0 & 1 & 00 & 01 & 10 & 11\\\hline
Even & (Even,0) & (Odd, 1) & (Even, 0) & (Odd, 1) & (Odd, 1) & (Even, 0)\\
Odd & (Odd,1) & (Even, 0) & (Odd, 1) & (Even, 0) & (Even, 0) & (Odd, 1)\\\hline
Same\ as & T_0 & T_1 & T_0 & T_1 & T_1 & T_0
\end{array}
$$

In this example, inputs are $X=B^*$.
$S=\{Even, Odd\}$ and the output($z$) is actually very straight forward that's one-to-one on the $S=\cases{Even: 0\\Odd: 1},where\ s_{in}, s_{out}\in S$.

$$
\cases{
T_0(Even)=(Even,0)\\
T_0(Odd)=(Odd,1)\\
}\\
\cases{
T_1(Even)=(Odd,1)\\
T_1(Odd)=(Even,0)\\
}\\
T=\{T_\lambda,T_0,T_1\}\\
[T;\cdot]\in Monoid, \forall s,t\in X, T_s\cdot T_t=T_{s\cdot_+t}=T_{st} \iff T(s\cdot_+ t)=T(s)\cdot T(t)\\
\therefore \cases {
T_0\cdot T_0 = T_{00} = T_0\\
T_0\cdot T_1 = T_{01} = T_1\\
T_1\cdot T_0 = T_{10} = T_1\\
T_1\cdot T_1 = T_{11} = T_0\\
}\iff
\begin{array}{lcc}
\cdot & T_0 & T_1\\\hline
T_0 & T_0 & T_1\\\hline
T_1 & T_1 & T_0\\\hline
\end{array}
$$

The monoid of parity check machine is isomorphic to the monoid of $[\mathbb{Z}_2;+_2]$.

## The Machine of a Monoid

Any **finite monoid $[M;\cdot]$** can be represented in the form of a finite-state machine with input and state sets equal to $M$.

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**.

### Machine of a Monoid

:::info
$[M ; \cdot]$ is a finite monoid.
The machine of $M$, denoted $m(M)$, is the state machine with
- **state set $M$**
- **input set $M$**
- **next-state function $t : M\times M \to M$ defined by $t(s,x) = s\cdot x$**
$$
m(M)\iff\cases{
[M;\cdot]\in finite\ monoid\\
s,x\in M\\
s:state\\
x:input\\
t:M\times M\to M\implies t(s,x)=s\cdot x
}
$$
:::

### Machine of the $[\mathbb{Z}_2;+_2]$ monoid

$$
m(\mathbb{Z}_2)\iff\cases{
s, x\in\mathbb{Z}_2\\
s: state\\
x: input\\
t: \mathbb{Z}_2\times\mathbb{Z}_2\to \mathbb{Z}_2\implies t(s,x)=s+_2 x
}
$$

digraph {
graph [bgcolor=transparent];
node[fontcolor="#888888";color="#888888"];
edge [color="#888800";fontcolor="#aaaaaa"];
rankdir=LR;
0->0[xlabel="0/0"];
0->1[xlabel="1/1"];
1->0[label="1/0"];
1->1[label="0/1"];
}

###### tags: `math`