§E15.2正規言語

証明. 正規表現の構成に関する帰納法を用いる。各段階で、すでに構成したオートマトンの状態集合は互いに素であるとする。以下で「新しい状態」とは、すでに用いたどの状態とも異なる状態を意味する。

空集合の場合。新しい二状態$u_r,v_r$を取り、遷移を一つも置かない。$u_r$から$v_r$へ至る経路が存在しないため、$L(N_r)=\emptyset=L(\emptyset)$である。

空語の場合。新しい二状態$u_r,v_r$を取り、遷移$u_r\xrightarrow{\varepsilon}v_r$だけを置く。初期状態から受理状態へ至る経路のラベルは$\varepsilon$だけであるから、$L(N_r)=\{\varepsilon\}=L(\varepsilon)$である。

一文字の場合。$a\in\Sigma$に対して新しい二状態$u_r,v_r$を取り、遷移$u_r\xrightarrow{a}v_r$だけを置く。このオートマトンは$a$だけを受理するため、$L(N_r)=\{a\}=L(a)$である。

和の場合。$r=(r_1\mid r_2)$とする。帰納法の仮定から得た$N_{r_1},N_{r_2}$に、新しい二状態$u_r,v_r$を加える。各部分オートマトンの遷移に加えて、

を置く。

$u_r$から$v_r$へ至る経路は、最初の遷移で二つの部分オートマトンのうち一方へ入り、その部分オートマトンの受理状態を経て$v_r$へ至る。二つの部分オートマトンの状態集合は互いに素であり、それぞれの受理状態から出る既存の遷移は存在しないため、経路が途中で一方から他方へ移ることはない。したがって

である。

連接の場合。$r=(r_1r_2)$とする。$N_{r_1},N_{r_2}$に新しい二状態$u_r,v_r$を加え、

を置く。

$u_r$から$v_r$へ至る任意の経路は、$N_{r_1}$の初期状態から受理状態へ至った後に、$N_{r_2}$の初期状態から受理状態へ至る。したがって、受理経路のラベルは$x\in L(N_{r_1})$と$y\in L(N_{r_2})$の連接$xy$である。逆に、そのような二つの受理経路を三本の新しい$\varepsilon$遷移によってつなぐと、ラベル$xy$の受理経路を得る。ゆえに

である。

Kleene スターの場合。$r=(r_1^*)$とする。$N_{r_1}$に新しい二状態$u_r,v_r$を加え、

を置く。

最初の遷移として$u_r\xrightarrow{\varepsilon}v_r$を選ぶ経路のラベルは$\varepsilon$である。この直接の遷移を選ばない受理経路は$N_{r_1}$を有限回通過し、各通過の後に次の通過を始めるか$v_r$へ移る。したがって、$N_{r_1}$を$n$回通過する受理経路のラベルは$L(N_{r_1})^n$に属する。逆に、任意の$n\geq 0$と$x_1,\ldots,x_n\in L(N_{r_1})$に対して、各$x_i$を読む受理経路を$v_{r_1}\xrightarrow{\varepsilon}u_{r_1}$で順につなぐと、ラベル$x_1\cdots x_n$の受理経路を得る。したがって

である。

いずれの構成でも$u_r$と$v_r$は異なる新しい状態であり、$u_r$へ入る遷移と$v_r$から出る遷移を置いていない。各段階で加える状態と遷移の個数は有限である。以上により、四条件がすべて成り立つ。▨

証明.$k$に関する帰納法を用いる。

$k=0$の場合、中間状態をもたない経路は長さ$0$または長さ$1$である。長さ$0$の経路が$q_i$から$q_j$へ至るのは$i=j$の場合に限り、そのラベルは$\varepsilon$である。長さ$1$の経路のラベルは、$\delta(q_i,a)=q_j$を満たす文字$a$である。したがって、該当するラベル全体は$L(R_{ij}^{(0)})$に等しい。

$k-1$について主張が成り立つと仮定する。$q_i$から$q_j$へ至り、中間状態が$\{q_1,\ldots,q_k\}$に属する経路$\pi$を取る。

$q_k$が$\pi$の中間状態として現れない場合、帰納法の仮定により、$\pi$のラベルは$L(R_{ij}^{(k-1)})$に属する。

$q_k$が$\pi$の中間状態として現れる場合、$\pi$を$q_k$が現れる各位置で切断する。最初の部分は$q_i$から$q_k$へ至り、最後の部分は$q_k$から$q_j$へ至る。両者の間には、$q_k$から$q_k$へ戻る経路が有限個並ぶ。切断後の各経路は$q_k$を中間状態として含まず、他の中間状態は$\{q_1,\ldots,q_{k-1}\}$に属する。帰納法の仮定により、最初の部分、各中間部分、最後の部分のラベルはそれぞれ

に属する。よって、$\pi$のラベルは

に属する。以上により、対象となる経路のすべてのラベルが$L(R_{ij}^{(k)})$に属する。

逆に、$L(R_{ij}^{(k-1)})$に属する語は、帰納法の仮定から、許される中間状態が$\{q_1,\ldots,q_{k-1}\}$に属する経路のラベルである。また、

に属する語は、帰納法の仮定が与える一つの$q_i$から$q_k$への経路、有限個の$q_k$から$q_k$への経路、および一つの$q_k$から$q_j$への経路を連結して得られる経路のラベルである。連結後の経路の中間状態は$\{q_1,\ldots,q_k\}$に属する。したがって、$L(R_{ij}^{(k)})$の各語は主張にある経路のラベルである。二つの包含が成り立つため、帰納不変量が成立する。▨

証明.$Q=\{q_1,\ldots,q_n\}$と番号づけ、補題 3.1の正規表現を構成する。$F=\emptyset$ならば$r_A:=\emptyset$とする。$F\neq\emptyset$ならば

と定める。

すべての状態が$\{q_1,\ldots,q_n\}$に属するため、補題 3.1により、$L(R_{\ell j}^{(n)})$は$q_\ell$から$q_j$へ至るすべての経路のラベル全体である。DFA$A$が語$w$を受理することは、$q_\ell$からある受理状態$q_j\in F$へ至るラベル$w$の経路が存在することと同値である。したがって

である。$F=\emptyset$の場合にも両辺は空集合である。▨

証明.(1)$\Rightarrow$(2)は命題 2.1によって従う。(2)$\Rightarrow$(3)は、§E15.1 系 4.2によって従う。(3)$\Rightarrow$(1)は命題 3.2によって従う。したがって三条件は同値である。▨

証明.$z\in\Sigma^*$を任意に取る。$az\in\Sigma^*$に対して$x\sim_L y$を適用すると、$x(az)\in L$と$y(az)\in L$は同値である。$x(az)=(xa)z$かつ$y(az)=(ya)z$であるから、$(xa)z\in L$と$(ya)z\in L$は同値である。$z$は任意であったから$xa\sim_L ya$である。▨

証明.$L$が正規であるとする。$L=L(A)$となる DFA$A=(Q,\Sigma,\delta,q_0,F)$を取り、§E15.1 定義 1.2の拡張遷移関数$\widehat{\delta}$を用いて$\varphi:\Sigma^*\to Q$を$\varphi(x):=\widehat{\delta}(q_0,x)$で定める。

$\varphi(x)=\varphi(y)$と仮定する。語の長さに関する帰納法により、任意の$z\in\Sigma^*$について$\widehat{\delta}(q_0,xz)=\widehat{\delta}(\varphi(x),z)$が成り立つ。実際、$z=\varepsilon$では両辺とも$\varphi(x)$であり、$z=z'a$では

となる。したがって、任意の$z$について

であり、§E15.1 定義 1.4により$xz\in L$と$yz\in L$は同値である。よって$x\sim_L y$である。

いま、$\varphi$の像$\varphi(\Sigma^*)\subseteq Q$から$\Sigma^*/{\sim_L}$への対応$\varphi(x)\mapsto[x]$を考える。前段落により、この対応は代表元の取り方によらず定まる。また、各同値類$[x]$は$\varphi(x)$の像であるから、この対応は全射である。ゆえに

であり、指数は有限である。

逆に、$L$の指数が有限であるとする。$x$の同値類を$[x]$と書き、

と定める。$\delta_L$が代表元の取り方によらないことは補題 5.2による。$F_L$が代表元の取り方によらないことは、$x\sim_L y$に$z=\varepsilon$を適用すると$x\in L$と$y\in L$が同値になることによる。仮定より$Q_L$は有限であるから、$A_L:=(Q_L,\Sigma,\delta_L,q_L,F_L)$は DFA である。

語の長さに関する帰納法により$\widehat{\delta_L}(q_L,w)=[w]$である。実際、$w=\varepsilon$では両辺が$[\varepsilon]$であり、$w=w'a$では

である。したがって

となる。ここで二つ目の同値は、$[w]\in F_L$が「ある$x\in L$について$w\sim_L x$」を意味し、その場合に$z=\varepsilon$を取れば$w\in L$が従うことによる。よって$L=L(A_L)$であり、$L$は正規言語である。▨

証明. 前半は定理 5.3 (Myhill–Nerode の定理)の証明前半で示した不等式$|\Sigma^*/{\sim_L}|\le|Q|$そのものである。後半は$A_L$の状態集合が$\Sigma^*/{\sim_L}$であることによる。▨

証明.$i\ne j$である非負整数$i,j$を取り、後続語として$z=b^i$を選ぶ。$a^ib^i\in L$である一方、$a^jb^i$は$j\ne i$であるから$L$に属さない。したがって$a^i\not\sim_L a^j$である。

ゆえに$a^0,a^1,a^2,\ldots$は互いに異なる$\sim_L$の同値類に属し、$L$の指数は無限である。定理 5.3 (Myhill–Nerode の定理)により、$L$は正規言語ではない。▨

証明.定義 1により、$L=L(A)$となる DFA$A=(Q,\Sigma,\delta,q_0,F)$を取る。$N:=|Q|$と置く。$Q$は空でない有限集合であるから$N\ge 1$である。

$w=a_1a_2\cdots a_m\in L$が$m\ge N$を満たすとする。$0\le k\le N$に対して

と置く。$p_0,\ldots,p_N$は$Q$の元$N+1$個であり、$|Q|=N$であるから、鳩の巣原理により$p_j=p_k$となる$0\le j<k\le N$が存在する。

と置く。$|xy|=k\le N$であるから条件 (a)が成り立ち、$j<k$であるから$y\ne\varepsilon$であり条件 (b)が成り立つ。

条件 (c)を示す。§E15.1 補題 1.3により

である。したがって、$i$に関する帰納法により、すべての$i\ge 0$について$\widehat{\delta}(p_j,y^i)=p_j$が成り立つ。実際、$i=0$では$y^0=\varepsilon$であり$\widehat{\delta}(p_j,\varepsilon)=p_j$である。$i$で成り立つとすると、再び§E15.1 補題 1.3により$\widehat{\delta}(p_j,y^{i+1})=\widehat{\delta}(\widehat{\delta}(p_j,y^i),y)=\widehat{\delta}(p_j,y)=p_j$である。

同じ補題を二度用いると、任意の$i\ge 0$について

を得る。$w\in L=L(A)$であるから$\widehat{\delta}(q_0,w)\in F$であり、§E15.1 定義 1.4により$xy^iz\in L$である。▨