正規言語

（文法からオートマトンへ）$G=(V,\Sigma,R,S)$ を右線形文法とする。状態集合を $V$ に新しい状態 $f$ と、各規則ごとの中間状態を加えたものとし、遷移を次のように定める。規則 $r\colon A\to a_1a_2\cdots a_kB$（$k\ge0$、$a_i\in\Sigma$、$B\in V$）に対し、$k\ge1$ なら新しい状態 $r_1,\ldots,r_{k-1}$ を用意して遷移 $A\xrightarrow{a_1}r_1\xrightarrow{a_2}r_2\cdots r_{k-1}\xrightarrow{a_k}B$ を置き（$k=1$ なら $A\xrightarrow{a_1}B$）、$k=0$ なら $\varepsilon$ 遷移 $A\xrightarrow{\varepsilon}B$ を置く。規則 $A\to a_1\cdots a_k$ に対しても同様に、終点を $f$ とした遷移の列（$k=0$ なら $A\xrightarrow{\varepsilon}f$）を置く。初期状態を $S$、受理状態集合を $\{f\}$ とした有限オートマトン $\mathcal{A}$ をとる。中間状態には対応する規則の遷移以外は出入りしないので、$\mathcal{A}$ において変数記号 $A$ から変数記号 $B$（または $f$）へ他の変数記号や $f$ を経由せずに至る経路は、ちょうど一つの規則 $A\to wB$（または $A\to w$）に対応し、そのラベルは $w$ である。
「$A\Rightarrow^{*}w$（$w\in\Sigma^{*}$）であることと、$\mathcal{A}$ において $A$ から $f$ へラベル $w$ の経路があることは同値」を示す。導出 $A\Rightarrow w_1A_1\Rightarrow w_1w_2A_2\Rightarrow\cdots\Rightarrow w_1\cdots w_{n-1}A_{n-1}\Rightarrow w_1\cdots w_n=w$ は、規則 $A\to w_1A_1$、$A_1\to w_2A_2$、$\ldots$、$A_{n-1}\to w_n$ の列にほかならず、これは上の対応により $A$ から $A_1$、$A_1$ から $A_2$、$\ldots$、$A_{n-1}$ から $f$ へのラベル $w_1,\ldots,w_n$ の経路の列に対応する。逆に $A$ から $f$ への経路を、通過する変数記号で区切れば、同じ対応により規則の列、したがって導出が得られる。$A=S$ とすれば $L(G)=L(\mathcal{A})$ である。
（オートマトンから文法へ）$L=L(\mathcal{A})$ とする。有限オートマトン の記事の命題（$\varepsilon$ 遷移の除去）により $\mathcal{A}=(Q,\Sigma,\Delta,q_0,F)$ は $\varepsilon$ 遷移を持たないとしてよい。変数記号の集合を $Q$、開始記号を $q_0$ とし、生成規則を
$$R:=\{\,p\to aq\mid (p,a,q)\in\Delta\,\}\cup\{\,p\to\varepsilon\mid p\in F\,\}$$
と定めた右線形文法 $G$ をとる。「$p\Rightarrow^{*}w$ であることと、$p$ から $F$ の元へラベル $w$ の経路があることは同値」を $|w|$ に関する帰納法で示す。$w=\varepsilon$ のとき、$p\Rightarrow^{*}\varepsilon$ となるのは規則 $p\to\varepsilon$ を使うときに限るので（他の規則は必ず記号を一つ生成する）、$p\in F$ と同値であり、これは長さ $0$ の経路の存在と同値である。$w=aw'$ のとき、$p\Rightarrow^{*}aw'$ の最初の一歩は $p\to aq$ の形で、続いて $q\Rightarrow^{*}w'$ である。帰納法の仮定により後者は $q$ から $F$ へのラベル $w'$ の経路の存在と同値であり、これに遷移 $(p,a,q)$ を前置すれば $p$ からのラベル $aw'$ の経路が得られる。逆も同様である。$p=q_0$ とおけば $L(G)=L(\mathcal{A})$ である。

$L$ を受理する DFA $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ をとり、$p:=|Q|$ とおく。$|w|\ge p$ なる $w=a_1a_2\cdots a_n\in L$（$n\ge p$）に対し、$q_i:=\delta(q_0,a_1\cdots a_i)$（$i=0,1,\ldots,n$）とおく。$q_0,q_1,\ldots,q_p$ は $p+1$ 個の状態からなり $Q$ の元は $p$ 個なので、鳩の巣原理により $q_i=q_j$ となる $0\le i< j\le p$ が存在する。
$x:=a_1\cdots a_i$、$y:=a_{i+1}\cdots a_j$、$z:=a_{j+1}\cdots a_n$ とおく。$|y|=j-i\ge1$（条件 1）、$|xy|=j\le p$（条件 2）である。$\delta(q_0,x)=q_i$、$\delta(q_i,y)=q_j=q_i$ であるから、$m$ に関する帰納法により $\delta(q_i,y^{m})=q_i$ がすべての $m\in\mathbb{N}$ について成り立つ。よって
$$\delta(q_0,xy^{m}z)=\delta(\delta(\delta(q_0,x),y^{m}),z)=\delta(q_i,z)=\delta(q_j,z)=\delta(q_0,w)=q_n\in F$$
であり、$xy^{m}z\in L$（条件 3）である。

$L_1=L(G_1)$、$L_2=L(G_2)$、$G_i=(V_i,\Sigma,R_i,S_i)$ を右線形文法とし、変数記号の名前を付け替えて $V_1\cap V_2=\emptyset$ としておく。右線形文法の導出では、文字列はつねに $xA$（$x\in\Sigma^{*}$、$A$ は変数記号）の形をしており、変数記号は一つしかないので、規則を適用する場所の選択はなく、導出はその規則の列によって定まる。
和集合：新しい開始記号 $S$ を用意し、$G_\cup:=(V_1\cup V_2\cup\{S\},\Sigma,R_1\cup R_2\cup\{S\to S_1,S\to S_2\},S)$ とする。$S$ からの導出は最初の一歩で $S_1$ か $S_2$ を選び、以後は $V_1$ の変数記号しか現れないか $V_2$ の変数記号しか現れないので、それぞれ $G_1$、$G_2$ の導出である。よって $L(G_\cup)=L_1\cup L_2$。
連接：$R_1$ の規則のうち右辺に変数記号を含まないもの $A\to w$（$w\in\Sigma^{*}$）をすべて $A\to wS_2$ に置き換えた規則集合を $R_1'$ とし、$G_\cdot:=(V_1\cup V_2,\Sigma,R_1'\cup R_2,S_1)$ とする。$G_\cdot$ における終端文字列の導出は、$V_1$ の変数記号だけが現れる区間と $V_2$ の変数記号だけが現れる区間に分かれ、境目はちょうど置き換えた規則 $A\to wS_2$ の適用である。前半の区間で $A\to wS_2$ を $A\to w$ に戻せば $G_1$ の導出 $S_1\Rightarrow^{*}u$（$u\in L_1$）が得られ、後半は $G_2$ の導出 $S_2\Rightarrow^{*}v$（$v\in L_2$）である。よって生成される文字列は $uv$ の形であり、逆に $u\in L_1$、$v\in L_2$ の導出をこの順につなげば $uv$ が導出される。よって $L(G_\cdot)=L_1L_2$。
Kleene 閉包：$L=L(G)$、$G=(V,\Sigma,R,S)$ とし、新しい開始記号 $S'\notin V$ を用意して
$$R_{*}:=R\cup\{\,A\to wS\mid (A\to w)\in R,\ w\in\Sigma^{*}\,\}\cup\{S'\to S,\ S'\to\varepsilon\},\qquad G_{*}:=(V\cup\{S'\},\Sigma,R_{*},S')$$
とおく。元の規則 $A\to w$（終了規則）はそのまま残し、同じ文字列を生成したあと $S$ から再開する規則 $A\to wS$（再開規則）を加えている。$S'\Rightarrow\varepsilon$ により $\varepsilon\in L(G_{*})$ である。$S'\Rightarrow S$ から始まる終端文字列の導出を、再開規則の適用の箇所で区切ると、各区間は $S$ から始まり、$R$ の規則を用いて $S\Rightarrow^{*}xA$ と進んだのち、再開規則 $A\to wS$（最後の区間では終了規則 $A\to w$）を適用したものである。再開規則を対応する終了規則に戻せば各区間は $G$ の導出 $S\Rightarrow^{*}xw$ になるので、生成される文字列は $L$ の元を有限個並べたもの、すなわち $L^{*}$ の元である。逆に $u_1,\ldots,u_n\in L$ に対し、$u_1,\ldots,u_{n-1}$ の $G$ における導出の最後の一歩を再開規則に替えてつなぎ、$u_n$ の導出で終えれば $S'\Rightarrow S\Rightarrow^{*}u_1\cdots u_n$ が得られる。よって $L(G_{*})=L^{*}$。
いずれの構成でも、規則の右辺は「終端記号の列の末尾に高々一つの変数記号」という形を保つので、得られる文法は右線形である。

thm-regular-language-kleene により、$L_1$、$L_2$ を受理する DFA $\mathcal{A}_1$、$\mathcal{A}_2$ がとれる。有限オートマトン の記事の命題（積構成と補集合）により、$\mathcal{A}_1$ の受理状態集合を入れ替えた DFA は $\Sigma^{*}\setminus L_1$ を、積 $\mathcal{A}_1\times\mathcal{A}_2$ は $L_1\cap L_2$ を受理する。よって両者は正規言語であり、$L_1\setminus L_2=L_1\cap(\Sigma^{*}\setminus L_2)$ も正規言語である。補集合の構成には完全な DFA が必要であること（NFA や不完全な DFA の受理状態を入れ替えても補集合にならないこと）は 有限オートマトン の記事の注意を参照。

鏡像：$L$ を受理する $\varepsilon$ 遷移のない有限オートマトン $\mathcal{A}=(Q,\Sigma,\Delta,q_0,F)$ をとる（有限オートマトン の記事の命題（$\varepsilon$ 遷移の除去））。新しい初期状態 $s\notin Q$ を用意し、
$$\Delta^{\mathrm{R}}:=\{\,(q,a,p)\mid(p,a,q)\in\Delta\,\}\cup\{\,(s,\varepsilon,f)\mid f\in F\,\},\qquad \mathcal{A}^{\mathrm{R}}:=(Q\cup\{s\},\Sigma,\Delta^{\mathrm{R}},s,\{q_0\})$$
とおく。$\mathcal{A}$ における $q_0$ から $f\in F$ へのラベル $a_1\cdots a_n$ の経路 $q_0,p_1,\ldots,p_{n-1},f$ を逆にたどれば、$\mathcal{A}^{\mathrm{R}}$ における $f$ から $q_0$ へのラベル $a_n\cdots a_1$ の経路が得られ、先頭に $s\xrightarrow{\varepsilon}f$ を付ければ受理経路になる。逆に $\mathcal{A}^{\mathrm{R}}$ の受理経路は $s\xrightarrow{\varepsilon}f$ で始まり、以後は $\Delta$ の遷移を逆向きにたどるので、逆にたどり直せば $\mathcal{A}$ の受理経路になる。よって $L(\mathcal{A}^{\mathrm{R}})=L^{\mathrm{R}}$。
商：$L$ を受理する DFA $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ をとる。左商については、$I_K:=\{\,\delta(q_0,u)\mid u\in K\,\}\subset Q$ とおき、新しい初期状態 $s$ から $I_K$ の各状態への $\varepsilon$ 遷移を加えた有限オートマトン $\mathcal{A}_K$ を考える。$v$ が $\mathcal{A}_K$ で受理されることは、ある $q\in I_K$ について $\delta(q,v)\in F$ となること、すなわちある $u\in K$ について $\delta(q_0,uv)\in F$、つまり $uv\in L$ となることと同値である。よって $L(\mathcal{A}_K)=K^{-1}L$。右商については、受理状態集合を $F_K:=\{\,q\in Q\mid\exists v\in K,\ \delta(q,v)\in F\,\}$ に取り替えた DFA を考えると、$u$ が受理されることは $\delta(q_0,u)\in F_K$、すなわちある $v\in K$ について $uv\in L$ となることと同値である。よってこの DFA は $LK^{-1}$ を受理する。$K$ が正規でなくても $I_K$、$F_K$ は $Q$ の部分集合であって有限に定まるので、これは存在証明として有効である（ただし $K$ の記述から $I_K$、$F_K$ を計算する手続きがあると主張しているわけではない）。

まず $\sim_L$ が同値関係であることは、定義が「$z$ を付けたときの $L$ への所属が一致する」という条件の同値関係であることから明らかであり、右不変性は、$x\sim_L y$ のとき任意の $z$ について $(xa)z=x(az)\in L\iff y(az)=(ya)z\in L$ となることから従う。
(1) から (2)：$L$ を受理する DFA $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ をとる。$\delta(q_0,x)=\delta(q_0,y)$ ならば、任意の $z$ について $\delta(q_0,xz)=\delta(\delta(q_0,x),z)=\delta(\delta(q_0,y),z)=\delta(q_0,yz)$ なので $xz\in L\iff yz\in L$、すなわち $x\sim_L y$ である。したがって「同じ状態 $\delta(q_0,x)$ に着く」という同値関係は $\sim_L$ を細分する（その各同値類は $\sim_L$ のある同値類に含まれる）。この同値関係の類は高々 $|Q|$ 個なので、$\sim_L$ の同値類の個数も $|Q|$ 以下であり、有限である。
(2) から (1)：同値類全体の有限集合 $Q:=\Sigma^{*}/{\sim_L}$ を状態集合とし、$x$ の同値類を $[x]$ と書いて
$$\delta([x],a):=[xa],\qquad q_0:=[\varepsilon],\qquad F:=\{\,[x]\mid x\in L\,\}$$
と定める。$\delta$ は右不変性により代表元の取り方によらず定まり、$F$ も矛盾なく定まる（$x\sim_L y$ なら $z=\varepsilon$ をとって $x\in L\iff y\in L$）。$w$ に関する帰納法により $\delta([x],w)=[xw]$ であるから、$\delta(q_0,w)=[w]$ であり、$w$ が受理されることは $[w]\in F$、すなわち $w\in L$ と同値である。よってこの DFA は $L$ を受理し、thm-regular-language-kleene により $L$ は正規である。
最後の主張：(1) から (2) の議論により任意の DFA の状態数は同値類の個数以上であり、(2) から (1) で構成した DFA の状態数はちょうど同値類の個数である。

まず次の補題を示す。補題（規則の右辺を鏡像にした文法は鏡像言語を生成する）：規則がすべて $A\to\alpha$（$A\in V$、$\alpha\in(V\cup\Sigma)^{*}$）の形である任意の文法（右線形文法・左線形文法・文脈自由文法のいずれでもよい）$G=(V,\Sigma,R,S)$ に対し、各規則の右辺を鏡像に置き換えた文法を $G^{\mathrm{R}}:=(V,\Sigma,\{A\to\alpha^{\mathrm{R}}\mid A\to\alpha\in R\},S)$ とおくと、$L(G^{\mathrm{R}})=L(G)^{\mathrm{R}}$ である。実際、$G$ の導出 $\alpha_0\Rightarrow\alpha_1\Rightarrow\cdots\Rightarrow\alpha_n$ の各文字列を鏡像に置き換えると、規則 $A\to\alpha$ による置き換え $\gamma A\delta\Rightarrow\gamma\alpha\delta$ は $\delta^{\mathrm{R}}A\gamma^{\mathrm{R}}\Rightarrow\delta^{\mathrm{R}}\alpha^{\mathrm{R}}\gamma^{\mathrm{R}}$、すなわち規則 $A\to\alpha^{\mathrm{R}}$ による置き換えになるので、$G^{\mathrm{R}}$ の導出 $S\Rightarrow^{*}\alpha_n^{\mathrm{R}}$ が得られる。逆も同様（$(G^{\mathrm{R}})^{\mathrm{R}}=G$）であるから、$w\in L(G)$ と $w^{\mathrm{R}}\in L(G^{\mathrm{R}})$ は同値であり、$L(G^{\mathrm{R}})=L(G)^{\mathrm{R}}$ である。
$G$ が右線形なら $G^{\mathrm{R}}$ は左線形であり（$(wB)^{\mathrm{R}}=Bw^{\mathrm{R}}$）、$G$ が左線形なら $G^{\mathrm{R}}$ は右線形である。
$L$ が正規なら、prop-regular-language-closure-reversal-quotient により $L^{\mathrm{R}}$ も正規なので右線形文法 $G$ で $L(G)=L^{\mathrm{R}}$ となるものがあり、左線形文法 $G^{\mathrm{R}}$ が $L(G^{\mathrm{R}})=(L^{\mathrm{R}})^{\mathrm{R}}=L$ を生成する。逆に $L$ が左線形文法 $G$ で生成されるなら、右線形文法 $G^{\mathrm{R}}$ が $L^{\mathrm{R}}$ を生成するので $L^{\mathrm{R}}$ は正規であり、再び鏡像の閉包性から $L=(L^{\mathrm{R}})^{\mathrm{R}}$ も正規である。

右線形文法は、変数記号の名前を $A_1,A_2,\ldots$ と付け替えれば、有限個の記号からなる有限の文字列として書き表せるので、右線形文法全体は可算集合である（形式言語 の記事の命題（言語の個数）の証明と同じ番号づけによる）。各文法は一つの言語を定めるから正規言語は高々可算個であり、ex-regular-language-finite により有限言語はすべて正規で無限個あるので可算無限個である。一方 $\Sigma^{*}$ の部分集合全体は非可算であるから、正規でない言語が存在する。