形式言語

結合律：$u=a_1\cdots a_k$、$v=b_1\cdots b_l$、$w=c_1\cdots c_m$ とすると、$(uv)w$ も $u(vw)$ も記号を $a_1,\dots,a_k,b_1,\dots,b_l,c_1,\dots,c_m$ の順に並べた同じ文字列である。単位元：$\varepsilon$ は記号を持たないので、任意の $w$ について $\varepsilon w=w\varepsilon=w$ である。
拡張の存在：$\bar f(a_1\cdots a_n):=f(a_1)f(a_2)\cdots f(a_n)$（$M$ における積。$n=0$ のときは $M$ の単位元 $1_M$）と定める。文字列の記号への分解 $w=a_1\cdots a_n$ は一意である（文字列とは記号の有限列そのものである）から、$\bar f$ は矛盾なく定まる。$u=a_1\cdots a_k$、$v=b_1\cdots b_l$ に対し $\bar f(uv)=f(a_1)\cdots f(a_k)f(b_1)\cdots f(b_l)=\bar f(u)\bar f(v)$ であり、$\bar f(\varepsilon)=1_M$ だから $\bar f$ はモノイドの準同型写像で、$\bar f(a)=f(a)$ を満たす。
一意性：$g\colon\Sigma^{*}\to M$ が $f$ を拡張する準同型写像なら、$n$ に関する帰納法により $g(a_1\cdots a_n)=g(a_1)\cdots g(a_n)=f(a_1)\cdots f(a_n)=\bar f(a_1\cdots a_n)$ である（$n=0$ では $g(\varepsilon)=1_M=\bar f(\varepsilon)$）。よって $g=\bar f$ である。

1. $(L_1L_2)L_3$ の元は $(uv)w$（$u\in L_1$、$v\in L_2$、$w\in L_3$）の形の文字列全体であり、$L_1(L_2L_3)$ の元は $u(vw)$ の形の文字列全体である。prop-formal-language-free-monoid の結合律により両者は一致する。$\{\varepsilon\}L=\{\varepsilon w\mid w\in L\}=L$ であり、$L\{\varepsilon\}=L$ も同様。$\emptyset L$ の元は $uv$（$u\in\emptyset$）の形だが $u$ は存在しないので $\emptyset L=\emptyset$ であり、$L\emptyset=\emptyset$ も同様。
2. $w\in L_1(L_2\cup L_3)$ とは、ある $u\in L_1$ と $v\in L_2\cup L_3$ で $w=uv$ となることであり、$v\in L_2$ なら $w\in L_1L_2$、$v\in L_3$ なら $w\in L_1L_3$ である。逆の包含も同様で、右からの分配も同じ議論による。同じ議論により、連接は任意個の和集合と交換する：$L\left(\bigcup_{i}M_i\right)=\bigcup_{i}LM_i$。
3. $L^{m}L^{n}=L^{m+n}$ を $n$ に関する帰納法で示す。$n=0$ では (1) により $L^{m}\{\varepsilon\}=L^{m}$。$n\to n+1$ では $L^{m}L^{n+1}=L^{m}(L^{n}L)=(L^{m}L^{n})L=L^{m+n}L=L^{m+n+1}$（結合律と帰納法の仮定）。次に $L^{*}L^{*}=L^{*}$：$w\in L^{*}L^{*}$ なら $w=uv$、$u\in L^{m}$、$v\in L^{n}$ となる $m,n$ があり、$w\in L^{m}L^{n}=L^{m+n}\subset L^{*}$。逆に $w\in L^{*}$ なら $w=w\varepsilon\in L^{*}L^{0}\subset L^{*}L^{*}$。最後に $(L^{*})^{*}=L^{*}$：$L^{*}=(L^{*})^{1}\subset(L^{*})^{*}$ である。逆に $(L^{*})^{n}\subset L^{*}$ を $n$ に関する帰納法で示せばよい。$n=0$ では $\{\varepsilon\}=L^{0}\subset L^{*}$、$n\to n+1$ では $(L^{*})^{n+1}=(L^{*})^{n}L^{*}\subset L^{*}L^{*}=L^{*}$。
4. 2. の最後の注意により $LL^{*}=\bigcup_{n}LL^{n}=\bigcup_{n}L^{1+n}=L^{+}$ であり、$L^{*}L=\bigcup_n L^{n}L=\bigcup_n L^{n+1}=L^{+}$。$L^{*}=L^{0}\cup\bigcup_{n\ge1}L^{n}=\{\varepsilon\}\cup L^{+}$ であり、最後の式は $L^{+}=LL^{*}$ から従う。

1. $(uv)^{\mathrm{R}}=v^{\mathrm{R}}u^{\mathrm{R}}$ を $|v|$ に関する帰納法で示す。$v=\varepsilon$ なら両辺とも $u^{\mathrm{R}}$ である。$v=v'a$（$a\in\Sigma$）なら、定義と帰納法の仮定により $(uv'a)^{\mathrm{R}}=a\,(uv')^{\mathrm{R}}=a\,v'^{\mathrm{R}}u^{\mathrm{R}}=(v'a)^{\mathrm{R}}u^{\mathrm{R}}$。次に $(u^{\mathrm{R}})^{\mathrm{R}}=u$ を $|u|$ に関する帰納法で示す。$u=\varepsilon$ は明らか。$u=u'a$ なら $(u^{\mathrm{R}})^{\mathrm{R}}=(a\,u'^{\mathrm{R}})^{\mathrm{R}}=(u'^{\mathrm{R}})^{\mathrm{R}}a^{\mathrm{R}}=u'a=u$（いま示した式と $a^{\mathrm{R}}=a$ を用いた）。長さが保たれることは定義から明らかである。
2. $(L_1L_2)^{\mathrm{R}}=\{(uv)^{\mathrm{R}}\mid u\in L_1,v\in L_2\}=\{v^{\mathrm{R}}u^{\mathrm{R}}\mid u\in L_1,v\in L_2\}=L_2^{\mathrm{R}}L_1^{\mathrm{R}}$。和集合との交換は明らか。$(L^{n})^{\mathrm{R}}=(L^{\mathrm{R}})^{n}$ が $n$ に関する帰納法で従い（$(L^{n+1})^{\mathrm{R}}=(L^{n}L)^{\mathrm{R}}=L^{\mathrm{R}}(L^{\mathrm{R}})^{n}=(L^{\mathrm{R}})^{n+1}$。最後の等号は prop-formal-language-operation-laws (3)）、両辺の $n$ についての和集合をとれば $(L^{*})^{\mathrm{R}}=(L^{\mathrm{R}})^{*}$。$(L^{\mathrm{R}})^{\mathrm{R}}=L$ は (1) から従う。
3. $v\in u^{-1}L\iff uv\in L\iff v^{\mathrm{R}}u^{\mathrm{R}}\in L^{\mathrm{R}}\iff v^{\mathrm{R}}\in L^{\mathrm{R}}(u^{\mathrm{R}})^{-1}$ である。
   $w\mapsto w^{\mathrm{R}}$ は (1) により自分自身を逆写像とする全単射であり、$(uv)^{\mathrm{R}}=v^{\mathrm{R}}u^{\mathrm{R}}$ は反準同型性である。

$k:=|\Sigma|\ge1$ とする。長さ $n$ の文字列は $k^{n}$ 個で有限であり、$\Sigma^{*}=\bigcup_{n\in\mathbb{N}}\{w\mid |w|=n\}$ は有限集合の可算個の和集合だから可算である。実際、$\Sigma$ の記号に順序をつけ、長さの昇順に、同じ長さでは辞書式順に並べれば、$\Sigma^{*}$ の元を $\mathbb{N}$ で番号づける全単射 $i\mapsto w_i$ が具体的に得られる。また $\varepsilon,a,aa,aaa,\ldots$（$a\in\Sigma$）は互いに異なるので $\Sigma^{*}$ は無限集合である。
$\mathcal{P}(\Sigma^{*})$ が非可算であることはCantorの定理（集合からその冪集合への全射はない）から従う。直接示すなら、言語の列 $L_0,L_1,L_2,\ldots$ が任意に与えられたとき、上の番号づけを用いて $D:=\{\,w_i\mid w_i\notin L_i\,\}$ とおけば、各 $i$ について $w_i\in D\iff w_i\notin L_i$ だから $D\ne L_i$ であり、$D$ はどの $L_i$ とも異なる言語である。よって言語全体を番号づけることはできない。