Kleeneの定理(正規言語)

$\alpha$ の組み立てに関する帰納法（構造的帰納法）で示す。
基礎． 状態を $s,f$ の 2 つとし、$\emptyset$ には遷移なし、$\varepsilon$ には $s\xrightarrow{\varepsilon}f$、$a\in\Sigma$ には $s\xrightarrow{a}f$ だけを置く。受理言語はそれぞれ $\emptyset$、$\{\varepsilon\}$、$\{a\}$ で、どれも標準形である。
帰納． 標準形の $\mathcal A_\alpha$（初期状態 $s_\alpha$、受理状態 $f_\alpha$）と $\mathcal A_\beta$（同じく $s_\beta,f_\beta$）があるとし、状態の名前を付け替えて状態の集合を交わらないようにする。以下の構成で加える遷移はすべて $\varepsilon$ 遷移である。

• 連接 $\alpha\beta$． 2 つを合わせて $f_\alpha\xrightarrow{\varepsilon}s_\beta$ を加え、初期状態を $s_\alpha$、受理状態を $f_\beta$ とする。$\mathcal A_\alpha$ の状態から $\mathcal A_\beta$ の状態へ移る遷移はこの 1 本だけで、逆向きの遷移はない。よって $s_\alpha$ から $f_\beta$ への経路は、$\mathcal A_\alpha$ の中の $s_\alpha$ から $f_\alpha$ への経路、加えた遷移、$\mathcal A_\beta$ の中の $s_\beta$ から $f_\beta$ への経路をこの順につないだものであり、ラベルは $uv$（$u\in L(\alpha)$、$v\in L(\beta)$）である。逆にそのような $u,v$ から経路が作れる。
• 和 $\alpha+\beta$． 新しい状態 $s,f$ と $s\xrightarrow{\varepsilon}s_\alpha$、$s\xrightarrow{\varepsilon}s_\beta$、$f_\alpha\xrightarrow{\varepsilon}f$、$f_\beta\xrightarrow{\varepsilon}f$ を加え、初期状態を $s$、受理状態を $f$ とする。$\mathcal A_\alpha$ と $\mathcal A_\beta$ の間を移る遷移はないので、$s$ から $f$ への経路は一方の部品の中の $s_\alpha$ から $f_\alpha$（または $s_\beta$ から $f_\beta$）への経路を通り、ラベルは $L(\alpha)\cup L(\beta)$ の元である。逆も成り立つ。
• Kleene 閉包 $\alpha^{*}$． 新しい状態 $s,f$ と $s\xrightarrow{\varepsilon}s_\alpha$、$s\xrightarrow{\varepsilon}f$、$f_\alpha\xrightarrow{\varepsilon}f$、$f_\alpha\xrightarrow{\varepsilon}s_\alpha$ を加え、初期状態を $s$、受理状態を $f$ とする。$f$ から出る遷移はないので、$s$ から $f$ への経路は $f$ に着いたところで終わる。その経路は、$s\xrightarrow{\varepsilon}f$ だけか、$s\xrightarrow{\varepsilon}s_\alpha$ で入り、$f_\alpha\xrightarrow{\varepsilon}s_\alpha$ で $0$ 回以上戻り、$f_\alpha\xrightarrow{\varepsilon}f$ で出るものである。$\mathcal A_\alpha$ の状態から出る加えた遷移は $f_\alpha$ から出るものだけなので、加えた遷移で区切った各区間は $\mathcal A_\alpha$ の中の $s_\alpha$ から $f_\alpha$ への経路であり、ラベルは $L(\alpha)$ の元である。よって受理言語は $L(\alpha)^{*}$ である。逆に $u_1,\dots,u_r\in L(\alpha)$ の経路をつなげば $u_1\cdots u_r$ の経路ができる（$r=0$ なら $s\xrightarrow{\varepsilon}f$）。
  どの場合も、新しい初期状態に入る遷移と新しい受理状態から出る遷移はなく、標準形である。状態の個数は、基礎では $2$、連接では増えず、和と Kleene 閉包では $2$ 増えるので、主張の上界が帰納法で従う。$\square$

1：途中の状態をもたない経路は、長さ $0$ の経路（$i=j$ のときだけあり、ラベル $\varepsilon$）と 1 本の遷移 $(q_i,a,q_j)$ からなる経路（ラベル $a$）である。長さ $2$ 以上の経路は番号 $1$ 以上の状態を途中で通るので、$0$ 経路ではない。
2：右辺 $\subset$ 左辺：$(k-1)$ 経路は $k$ 経路である。$q_i$ から $q_k$ への $(k-1)$ 経路、$q_k$ から $q_k$ への $(k-1)$ 経路を $0$ 個以上、$q_k$ から $q_j$ への $(k-1)$ 経路をこの順につなぐと、途中の状態は各区間の途中の状態（番号 $k-1$ 以下）とつなぎ目の $q_k$ なので、$k$ 経路になる。そのラベルは各区間のラベルの連接である。
左辺 $\subset$ 右辺：$k$ 経路が途中で $q_k$ を通らなければ $(k-1)$ 経路である。通るなら、途中で $q_k$ が現れる位置で経路を切る。最初の区間は $q_i$ から $q_k$ へ、間の区間は $q_k$ から $q_k$ へ、最後の区間は $q_k$ から $q_j$ への経路で、どの区間も途中で $q_k$ を通らないので $(k-1)$ 経路である。よってラベルは $R^{(k-1)}_{ik}\bigl(R^{(k-1)}_{kk}\bigr)^{*}R^{(k-1)}_{kj}$ に属する。
3：$n$ 経路はすべての経路なので、定義の受理言語そのものである。$\square$

1 から 2 は lem-kl-to-automaton である。
2 から 1 を示す。$\mathcal A$ を $L=L(\mathcal A)$ となる有限オートマトンとし、上のとおり $R^{(k)}_{ij}$ を定める。$k$ に関する帰納法で、$R^{(k)}_{ij}=L(\rho^{(k)}_{ij})$ となる正規表現 $\rho^{(k)}_{ij}$ を作る。$k=0$ では、lem-kl-paths の 1 の有限集合の元（$\Sigma$ の元と $\varepsilon$）を $+$ でつないだ式を $\rho^{(0)}_{ij}$ とし、元がなければ $\rho^{(0)}_{ij}:=\emptyset$ とする。$k\ge1$ では
$$ \rho^{(k)}_{ij}:=\rho^{(k-1)}_{ij}+\rho^{(k-1)}_{ik}\bigl(\rho^{(k-1)}_{kk}\bigr)^{*}\rho^{(k-1)}_{kj} $$
とすれば、lem-kl-paths の 2 と正規表現の言語の定義から $L(\rho^{(k)}_{ij})=R^{(k)}_{ij}$ である。lem-kl-paths の 3 により、$F=\{q_{j_1},\dots,q_{j_r}\}$ のとき $\alpha:=\rho^{(n)}_{1j_1}+\cdots+\rho^{(n)}_{1j_r}$（$F=\emptyset$ なら $\alpha:=\emptyset$）が $L(\alpha)=L$ を満たす。$\square$

$X=B^{*}C$ が方程式を満たすこと：$B^{*}=\{\varepsilon\}\cup BB^{*}$ なので $B^{*}C=C\cup B(B^{*}C)$ である。
逆に $X=BX\cup C$ とする。$X\supset B^{*}C$：$n$ についての帰納法で $X\supset B^{n}C$ を示す。$n=0$ では $X\supset C$ である。$X\supset B^{n}C$ なら $X\supset BX\supset B^{n+1}C$ である。$X\subset B^{*}C$：$w\in X$ の長さについての帰納法で示す。$w\in C$ なら $w\in B^{*}C$ である。そうでなければ $w\in BX$ なので $w=bv$（$b\in B$、$v\in X$）と書ける。$\varepsilon\notin B$ から $\lvert b\rvert\ge1$、$\lvert v\rvert< \lvert w\rvert$ であり、帰納法の仮定から $v\in B^{*}C$、よって $w\in BB^{*}C\subset B^{*}C$ である。$\square$

thm-kl-main により、$\mathcal R$ は正規表現で表される言語の全体に等しい。有限言語 $\{w_1,\dots,w_m\}$ は、各 $w_i=a_1\cdots a_l$ を式 $a_1\cdots a_l$（$l=0$ なら $\varepsilon$）として $w_1+\cdots+w_m$（$m=0$ なら $\emptyset$）で表される。$L(\alpha)\cup L(\beta)=L(\alpha+\beta)$、$L(\alpha)L(\beta)=L(\alpha\beta)$、$L(\alpha)^{*}=L(\alpha^{*})$ なので、$\mathcal R$ は 3 つの演算で閉じている。逆に、有限言語を含み 3 つの演算で閉じたクラス $\mathcal C$ は、$\alpha$ の組み立てに関する帰納法により、すべての $L(\alpha)$ を含む（$\emptyset$、$\{\varepsilon\}$、$\{a\}$ は有限言語である）。よって $\mathcal R\subset\mathcal C$ である。$\square$