Myhill–Nerodeの定理

同義語：Myhill–Nerode theoremMyhill-Nerodeの定理

概要

前提知識: 正規言語, 有限オートマトン, 同値関係, 形式言語

何を捉える定理か

正規言語は「有限個の状態だけを記憶として、文字列を左から読んで受理・非受理を決められる言語」である。では、言語 $L$ を判定するために、読み終えた接頭辞についてどれだけの情報を覚えておく必要があるのか。答えは「その接頭辞のあとに何を続ければ $L$ に入るか」という情報である。2 つの文字列 $x,y$ のあとに同じ文字列 $z$ を続けたとき、$xz$ と $yz$ が $L$ に入るか否かがどの $z$ についても一致するなら、判定のうえで $x$ と $y$ を区別する必要はない。
Myhill–Nerode の定理は、この「区別できない」という同値関係の類の個数が有限であることと、$L$ が正規であることとが同値であることを述べる。さらに、類の個数は $L$ を受理する決定性有限オートマトン（DFA）の状態数の最小値に等しく、状態数が最小の DFA は状態の名前の付け替えを除いてただ 1 つに定まる（最小オートマトン）。定理は正規性の必要十分条件なので、反復補題（正規言語の反復補題の定理「正規言語の反復補題」）では扱えない言語が正規でないことも示せ、正規であることの証明にも使える。
同じ考えを両側から行うと、言語の構文的合同とその商である構文モノイドが得られ、正規であることは構文モノイドが有限であることと同値になる（Myhill の定理、thm-mn-syntactic）。

定義

以下、$\Sigma$ は空でない有限集合（アルファベット）、$\Sigma^{*}$ はその上の文字列全体、$\varepsilon$ は空語、$|w|$ は文字列 $w$ の長さを表す。$\Sigma^{*}$ の部分集合を $\Sigma$ 上の言語という。
この記事で DFA というときは、遷移がすべての状態と記号について定まっているもの、すなわち $5$ つ組 $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$（$Q$ は有限集合、$\delta\colon Q\times\Sigma\to Q$ は写像、$q_0\in Q$、$F\subset Q$）を指す（有限オートマトンの定義「非決定性有限オートマトンと決定性有限オートマトン」）。$\delta$ を $\delta(q,\varepsilon)=q$、$\delta(q,wa)=\delta(\delta(q,w),a)$（$w\in\Sigma^{*}$、$a\in\Sigma$）により $Q\times\Sigma^{*}\to Q$ へ延ばすと、帰納法により
$$ \delta(q,uv)=\delta(\delta(q,u),v)\qquad(u,v\in\Sigma^{*}) $$
が成り立つ。$\mathcal{A}$ が受理する言語は $L(\mathcal{A})=\{\,w\mid\delta(q_0,w)\in F\,\}$ である。言語が正規であることと、ある DFA に受理されることとは同値である（正規言語の命題「右線形文法と有限オートマトンの同値性」と有限オートマトンの命題「部分集合構成」）。以下ではこの特徴づけを使う。

右合同と飽和

$\Sigma^{*}$ 上の同値関係 $\sim$ が右合同（right congruence）であるとは、$x\sim y$ ならば任意の $z\in\Sigma^{*}$ について $xz\sim yz$ となることをいう。$\sim$ の同値類の個数（無限のこともある）を $\sim$ の指数（index）という。言語 $L$ が $\sim$ の同値類の和集合であるとき、$\sim$ は $L$ を飽和するという。これは「$x\sim y$ かつ $x\in L$ ならば $y\in L$」と同値である。

$z$ を $1$ 文字ずつ付け足せばよいので、右合同であるためには「$x\sim y$ ならば任意の $a\in\Sigma$ について $xa\sim ya$」を確かめれば足りる。

Nerode同値関係

言語 $L\subset\Sigma^{*}$ と $x\in\Sigma^{*}$ に対し、$x$ による $L$ の左商（residual）を
$$ x^{-1}L:=\{\,z\in\Sigma^{*}\mid xz\in L\,\} $$
とおく。$\Sigma^{*}$ 上の関係 $\equiv_L$ を
$$ x\equiv_L y\ :\iff\ x^{-1}L=y^{-1}L\ \iff\ \forall z\in\Sigma^{*}\ (xz\in L\Leftrightarrow yz\in L) $$
で定め、$L$ の Nerode 同値関係という。$x\not\equiv_L y$ のとき、$xz$ と $yz$ の一方だけが $L$ に属する $z$ を、$x$ と $y$ を区別する語という。

Nerode同値関係は最も粗い飽和右合同

言語 $L$ について次が成り立つ。

$\equiv_L$ は $L$ を飽和する右合同である。
$\sim$ が $L$ を飽和する任意の右合同ならば、$x\sim y$ から $x\equiv_L y$ が従う。すなわち $\sim$ の各同値類は $\equiv_L$ のある同値類に含まれ、$\sim$ の指数は $\equiv_L$ の指数以上である。

1：$\equiv_L$ は「左商が等しい」という関係なので同値関係である。$x\equiv_L y$ と $z\in\Sigma^{*}$ をとると、任意の $w$ について $(xz)w=x(zw)\in L\iff y(zw)=(yz)w\in L$ なので $xz\equiv_L yz$ である。$x\equiv_L y$ かつ $x\in L$ なら、$z=\varepsilon$ をとって $y\in L$ である。
2：$x\sim y$ とし、$z\in\Sigma^{*}$ を任意にとる。右合同性から $xz\sim yz$ であり、$\sim$ は $L$ を飽和するので $xz\in L\iff yz\in L$ である。よって $x\equiv_L y$ である。後半は、$\sim$ の各同値類が $\equiv_L$ のただ 1 つの同値類に含まれることから、同値類の対応 $[x]_\sim\mapsto[x]_{\equiv_L}$ が全射になることによる。$\square$

主定理

Myhill–Nerode の定理

$\Sigma$ 上の言語 $L$ について、次の 3 条件は同値である。

$L$ は正規言語である。
$L$ を飽和する右合同で、指数が有限のものが存在する。
$\equiv_L$ の指数は有限である。
さらに、これらが成り立つとき、$L$ を受理する DFA の状態数の最小値は $\equiv_L$ の指数に等しい。

1 ⇒ 2。 $L$ を受理する DFA $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ をとり、$\Sigma^{*}$ 上の関係を
$$ x\sim_{\mathcal{A}}y\ :\iff\ \delta(q_0,x)=\delta(q_0,y) $$
で定める。これは同値関係で、同値類は到達する状態ごとに 1 つなので、指数は $|Q|$ 以下である。$x\sim_{\mathcal{A}}y$ なら任意の $z$ について $\delta(q_0,xz)=\delta(\delta(q_0,x),z)=\delta(\delta(q_0,y),z)=\delta(q_0,yz)$ なので右合同である。$x\sim_{\mathcal{A}}y$ かつ $x\in L$ なら $\delta(q_0,y)=\delta(q_0,x)\in F$ なので $y\in L$ であり、$\sim_{\mathcal{A}}$ は $L$ を飽和する。
2 ⇒ 3。 prop-mn-coarsest の 2 により、$\equiv_L$ の指数は 2 の右合同の指数以下で、有限である。
3 ⇒ 1。 $\equiv_L$ の同値類全体を $Q_L:=\Sigma^{*}/{\equiv_L}$ とし、$x$ の類を $[x]$ と書く。
$$ \delta_L([x],a):=[xa],\qquad q_L:=[\varepsilon],\qquad F_L:=\{\,[x]\mid x\in L\,\} $$
と定める。$\equiv_L$ が右合同なので $\delta_L$ は代表元によらず、$Q_L$ は仮定により有限集合である。$|w|$ についての帰納法で $\delta_L([x],w)=[xw]$ が成り立つ（$w=\varepsilon$ は自明で、$\delta_L([x],wa)=\delta_L([xw],a)=[xwa]$）。よって $\delta_L(q_L,w)=[w]$ である。$\equiv_L$ は $L$ を飽和するので、$[w]\in F_L$ と $w\in L$ とは同値である。したがって DFA
$$ \mathcal{A}_L:=(Q_L,\Sigma,\delta_L,q_L,F_L) $$
は $L$ を受理し、$L$ は正規である。
状態数。 1 ⇒ 2 と 2 ⇒ 3 の議論から、$L$ を受理する任意の DFA の状態数 $|Q|$ は $\sim_{\mathcal{A}}$ の指数以上であり、それは $\equiv_L$ の指数以上である。一方、3 ⇒ 1 の $\mathcal{A}_L$ の状態数はちょうど $\equiv_L$ の指数である。$\square$

3 ⇒ 1 で作った $\mathcal{A}_L$ を $L$ の最小オートマトン（minimal automaton）という。状態は「これまでに読んだ文字列の左商」そのものであり、$[x]$ は左商 $x^{-1}L$ と 1 対 1 に対応する。
条件 3 は正規でないことの証明に使いやすい形をしている。互いに区別できる文字列 $x_1,x_2,\dots$ が無限個あれば、すなわち $i\ne j$ ごとに $x_i$ と $x_j$ を区別する語があれば、$\equiv_L$ の指数は無限で、$L$ は正規でない。逆に、互いに区別できる $n$ 個の文字列が見つかれば、$L$ を受理する DFA は少なくとも $n$ 個の状態をもつ。

最小オートマトンの一意性

DFA $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ の状態 $q$ が到達可能であるとは、ある $w$ で $q=\delta(q_0,w)$ となることをいう。状態 $q$ が受理へ導く文字列の集合を $L_q:=\{\,v\mid\delta(q,v)\in F\,\}$ とおき、$L_p=L_q$ のとき $p$ と $q$ は同値な状態であるという。2 つの DFA $\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$、$\mathcal{A}'=(Q',\Sigma,\delta',q_0',F')$ について、写像 $h\colon Q\to Q'$ が
$$ h(q_0)=q_0',\qquad h(\delta(q,a))=\delta'(h(q),a),\qquad q\in F\iff h(q)\in F' $$
（$q\in Q$、$a\in\Sigma$）を満たすとき、$h$ を DFA の準同型といい、全単射な準同型を同型という。

最小オートマトンへの準同型と一意性

$\mathcal{A}=(Q,\Sigma,\delta,q_0,F)$ を言語 $L$ を受理する DFA とし、すべての状態が到達可能であるとする。

DFA の準同型 $h\colon\mathcal{A}\to\mathcal{A}_L$ がただ 1 つ存在し、それは $h(\delta(q_0,w))=[w]$ で与えられる全射である。
$h(p)=h(q)$ であることと、$p$ と $q$ が同値な状態であることとは同値である。
$|Q|$ が $\equiv_L$ の指数に等しいなら、$h$ は同型である。とくに、$L$ を受理する状態数最小の DFA は、すべて $\mathcal{A}_L$ とただ 1 つの同型で同型である。

1：$\delta(q_0,x)=\delta(q_0,y)$ なら、prf-mn-main の 1 ⇒ 2 により $x\equiv_L y$ なので、$h(\delta(q_0,w)):=[w]$ は矛盾なく定まり、すべての状態が到達可能なので $Q$ 全体で定義される。$h(q_0)=[\varepsilon]$、$h(\delta(\delta(q_0,w),a))=h(\delta(q_0,wa))=[wa]=\delta_L([w],a)$ であり、$\delta(q_0,w)\in F\iff w\in L\iff[w]\in F_L$ なので準同型である。像はすべての $[w]$ を含むので全射である。一意性：準同型 $h'$ は $h'(q_0)=[\varepsilon]$ と遷移との両立から、$|w|$ についての帰納法で $h'(\delta(q_0,w))=\delta_L([\varepsilon],w)=[w]$ を満たし、$h$ に一致する。
2：$p=\delta(q_0,x)$、$q=\delta(q_0,y)$ と書くと、$L_p=\{\,v\mid\delta(q_0,xv)\in F\,\}=x^{-1}L$、同様に $L_q=y^{-1}L$ である。よって $L_p=L_q$ は $x\equiv_L y$、すなわち $h(p)=h(q)$ と同値である。
3：全射 $h$ の定義域と値域の元の個数が等しいので $h$ は全単射であり、逆写像も準同型の条件を満たす。状態数最小の DFA は thm-mn-main により状態数が $\equiv_L$ の指数に等しく、もし到達可能でない状態があればそれを除いた DFA が $L$ を受理して状態数がより少なくなるので、すべての状態が到達可能である。同型の一意性は 1 の一意性による。$\square$

この定理から、与えられた DFA を最小化する手順が読み取れる。到達可能でない状態を取り除き、同値な状態を 1 つにまとめればよい。同値な状態は次のように有限の手続きで求められる。整数 $m\ge0$ について、長さ $m$ 以下のすべての $v$ で $\delta(p,v)\in F\iff\delta(q,v)\in F$ となるとき $p\equiv_mq$ と書く。$\equiv_0$ は「$F$ に属するか否か」で状態を 2 つに分ける同値関係であり、$p\equiv_{m+1}q$ は「$p\equiv_mq$ かつすべての $a\in\Sigma$ で $\delta(p,a)\equiv_m\delta(q,a)$」と同値である。

同値な状態の判定

$\mathcal{A}$ を状態数 $n\ge2$ の DFA とする。$\equiv_m$ と $\equiv_{m+1}$ が一致する $m$ があれば、$\equiv_m$ は状態の同値（$L_p=L_q$）に一致する。とくに $\equiv_{n-2}$ は状態の同値に一致する。

要点：最短の区別する語を、より短い区別する語に取り替えて矛盾を導き、類の個数の増加で $n-2$ を得る。

詳しい証明を開く

$\equiv_m=\equiv_{m+1}$ とする。$L_p\ne L_q$ となる $p,q$ があるとし、$\delta(p,w)\in F$ と $\delta(q,w)\in F$ の一方だけが成り立つ語 $w$ のうち長さ最小のものをとる。$|w|>m$ と仮定し、$w=uv$、$|v|=m+1$ と書くと、$p'=\delta(p,u)$、$q'=\delta(q,u)$ は $v$ で区別されるので $p'\not\equiv_{m+1}q'$、したがって $p'\not\equiv_mq'$ であり、長さ $m$ 以下の語 $v'$ で区別される。すると $uv'$ は $p$ と $q$ を区別し、$|uv'|<|w|$ となって最小性に反する。よって $|w|\le m$ で $p\not\equiv_mq$ である。逆に $L_p=L_q$ なら明らかに $p\equiv_mq$ である。

後半：$\equiv_{m+1}$ は $\equiv_m$ を細分するので、一致しない限り類の個数は少なくとも 1 増える。類の個数は $n$ 以下で、$\equiv_0$ の類は高々 2 個である。$\equiv_0$ の類が 1 個（$F=\emptyset$ または $F=Q$）なら $L_p$ はすべて等しく、$\equiv_0$ がすでに状態の同値である。2 個なら、$\equiv_0,\equiv_1,\dots$ が一致せずに増え続けられるのは高々 $n-2$ 回なので、ある $m\le n-2$ で $\equiv_m=\equiv_{m+1}$ となる。状態の同値は $\equiv_{n-2}$ を細分し、$\equiv_{n-2}$ は $\equiv_m$ を細分し、$\equiv_m$ は状態の同値に一致するので、$\equiv_{n-2}$ も状態の同値に一致する。$\square$

この判定を、状態の分割を細分していく形で実行するのが Moore の算法である。細分のたびに類を分け直す実装では計算量は $O(|\Sigma|\,n^{2})$ であり、Hopcroft の算法は $O(|\Sigma|\,n\log n)$ に改良する（SW10 §1.6.3）。

構文モノイドと Myhill の定理

Nerode 同値関係は文字列を右からだけ延ばして比べる。両側から延ばして比べると、連接と両立する同値関係が得られる。

構文的合同と構文モノイド

言語 $L$ に対し、$\Sigma^{*}$ 上の関係 $\approx_L$ を
$$ u\approx_Lv\ :\iff\ \forall x,y\in\Sigma^{*}\ (xuy\in L\Leftrightarrow xvy\in L) $$
で定め、$L$ の構文的合同（syntactic congruence）という。$\approx_L$ は同値関係で、$u\approx_Lv$、$u'\approx_Lv'$ ならば $uu'\approx_Lvv'$ を満たす（$xuu'y\in L\iff xvu'y\in L\iff xvv'y\in L$）。したがって商集合 $M(L):=\Sigma^{*}/{\approx_L}$ は連接から誘導される積でモノイドになる。これを $L$ の構文モノイド（syntactic monoid）という。

$u\approx_Lv$ なら $x=\varepsilon$ ととって $u\equiv_Lv$ なので、$\approx_L$ は $\equiv_L$ を細分する。また $\approx_L$ は右合同で、$L$ を飽和する（$x=y=\varepsilon$）。

Myhill の定理

言語 $L$ について、次は同値である。

$L$ は正規言語である。
構文モノイド $M(L)$ は有限である。
さらに $L$ が正規で、最小オートマトン $\mathcal{A}_L$ の状態数が $n$ ならば $|M(L)|\le n^{n}$ である。

2 ⇒ 1。 $\approx_L$ は $L$ を飽和する右合同で、指数 $|M(L)|$ は有限である。thm-mn-main の 2 ⇒ 1 により $L$ は正規である。
1 ⇒ 2 と評価。 $\mathcal{A}_L=(Q_L,\Sigma,\delta_L,q_L,F_L)$ をとり、$u\in\Sigma^{*}$ に写像 $f_u\colon Q_L\to Q_L$、$f_u(q)=\delta_L(q,u)$ を対応させる。$f_u=f_v$ と仮定する。任意の $x,y$ について
$$ \delta_L(q_L,xuy)=\delta_L(f_u(\delta_L(q_L,x)),y)=\delta_L(f_v(\delta_L(q_L,x)),y)=\delta_L(q_L,xvy) $$
であり、$\mathcal{A}_L$ は $L$ を受理するので $xuy\in L\iff xvy\in L$、すなわち $u\approx_Lv$ である。逆に $u\approx_Lv$ なら、任意の $x$ について $xu\equiv_Lxv$ なので $f_u([x])=[xu]=[xv]=f_v([x])$ である。よって $[u]\mapsto f_u$ は矛盾なく定まり、$M(L)$ から写像 $Q_L\to Q_L$ 全体の集合（元の個数 $n^{n}$）への単射を与え、$|M(L)|\le n^{n}$ である。$\square$

証明の写像 $[u]\mapsto f_u$ は実は、写像全体に積 $f\cdot g:=g\circ f$ を入れたモノイドへの単射準同型（$f_{uv}=f_v\circ f_u$ なので積の順序に注意）であり、$M(L)$ は $\mathcal{A}_L$ の遷移モノイドと同一視される（SW10 §1.6.5 Theorem 1.5、p. 33）。構文モノイドは $L$ に内在的に付随する有限代数系であり、正規言語のクラス分けを有限モノイドの性質で述べる代数的な理論の出発点になる。

例

3 の倍数の二進表現

$\Sigma=\{0,1\}$ とし、文字列 $w=w_1\cdots w_k$ の値を $\operatorname{val}(w)=\sum_iw_i2^{k-i}$（$\operatorname{val}(\varepsilon)=0$）とする。$L=\{\,w\mid\operatorname{val}(w)\equiv0\pmod 3\,\}$ を考える。$\operatorname{val}(xz)=2^{|z|}\operatorname{val}(x)+\operatorname{val}(z)$ なので、$x^{-1}L$ は $\operatorname{val}(x)$ を $3$ で割った余り $r$ だけで決まり、$\equiv_L$ の類は高々 $3$ 個である。余りの異なる $x,y$ は区別できる：$r=0$ と $r\ne0$ は $z=\varepsilon$ で、$r=1$ と $r=2$ は $z=1$ で区別される（$2\cdot1+1=3$、$2\cdot2+1=5$）。よって指数はちょうど $3$ で、最小オートマトンは状態 $\{0,1,2\}$、遷移 $\delta(r,a)=2r+a\bmod 3$、初期状態と受理状態 $0$ の DFA である。

後ろから n 番目が 1 である文字列

$n\ge1$ とし、$\Sigma=\{0,1\}$ 上の $L_n=\{\,w\mid|w|\ge n$ かつ $w$ の後ろから $n$ 番目の文字が $1\,\}$ を考える。$x\in\Sigma^{*}$ に対し、$0^{n}x$ の最後の $n$ 文字を $s(x)=s_1\cdots s_n$ とおく。$xz$ の長さが $n$ 以上なら $xz$ と $0^{n}xz$ の後ろから $n$ 番目の文字は一致し、$n$ 未満なら $xz\notin L_n$ で $0^{n}xz$ の後ろから $n$ 番目は $0$ である。どちらの場合も「$xz\in L_n$」は「$s(x)z$ の後ろから $n$ 番目が $1$」と同値なので、$x^{-1}L_n$ は $s(x)$ だけで決まる。$s(x)\ne s(y)$ で $i$ 番目が異なれば、$z=0^{i-1}$ をとると $s(x)z$ と $s(y)z$ の後ろから $n$ 番目はそれぞれ $s(x)_i$、$s(y)_i$ なので、$x$ と $y$ は区別される。$s$ は長さ $n$ の文字列すべてを値にとるので、$\equiv_{L_n}$ の指数は $2^{n}$ であり、$L_n$ を受理する DFA は $2^{n}$ 個以上の状態をもつ。他方、「どこかで $1$ を読んでからちょうど $n-1$ 文字読んで終わる」ことを推測する非決定性有限オートマトンは $n+1$ 個の状態で $L_n$ を受理する。部分集合構成（有限オートマトンの命題「部分集合構成」）による状態数の増加が、指数関数的に避けられない例である。

対応のとれた文字列

$\Sigma=\{a,b\}$、$L=\{\,a^{k}b^{k}\mid k\ge0\,\}$ とする。$i\ne j$ なら $a^{i}b^{i}\in L$、$a^{j}b^{i}\notin L$ なので、$z=b^{i}$ が $a^{i}$ と $a^{j}$ を区別する。$a^{0},a^{1},a^{2},\dots$ は互いに区別できるので、$\equiv_L$ の指数は無限で、$L$ は正規でない。

反復補題の条件を満たすが正規でない言語

$\Sigma=\{a,b,c\}$、$L=\{\,a^{i}b^{j}c^{k}\mid i,j,k\ge0,\ i=1\text{ ならば }j=k\,\}$ とする。$j\ne j'$ なら $z=c^{j}$ について $ab^{j}c^{j}\in L$、$ab^{j'}c^{j}\notin L$ なので、$ab^{0},ab^{1},ab^{2},\dots$ は互いに区別でき、$L$ は正規でない。
一方 $L$ は、正規言語の反復補題の定理「正規言語の反復補題」の結論を $p=2$ で満たす。$w=a^{i}b^{j}c^{k}\in L$、$|w|\ge2$ とする。$i=0$ なら $w$ の先頭の $1$ 文字を $y$ にとる（$y$ は $b$ か $c$）。$y$ を何回繰り返しても除いても $a$ を含まないので $L$ に属する。$i=1$ なら $y=a$ とすると $a^{m}b^{j}c^{j}$（$m\ge0$）はすべて $L$ に属する（$m\ne1$ では条件がなく、$m=1$ では $j=k$）。$i=2$ なら $y=aa$ とすると $a^{2m}b^{j}c^{k}$ の $a$ の個数は $1$ にならない。$i\ge3$ なら $y=a$ とすると $a$ の個数は $i-1+m\ge2$ である。いずれも $|xy|\le2$、$|y|\ge1$ で、$xy^{m}z\in L$（$m\ge0$）となる。したがって反復補題では $L$ が正規でないことを示せないが、Myhill–Nerode の定理なら示せる。

反例の表

thm-mn-main の条件 2 の 3 つの要請（右合同・有限指数・飽和）と、thm-mn-minimal-unique の決定性・遷移の完全性を 1 つずつ外す。

外す条件	反例	成り立たなくなること
右合同であること（thm-mn-main の 2）	$L=\{a^{k}b^{k}\}$ と、類が $L$ と $\Sigma^{*}\setminus L$ の $2$ つの同値関係（$a\sim aa$ だが $ab\in L$、$aab\notin L$ なので $ab\not\sim aab$）	2 ⇒ 1（指数 $2$ で $L$ を飽和するが $L$ は正規でない）
指数が有限であること（同）	等号の関係 $x\sim y\iff x=y$ と $L=\{a^{k}b^{k}\}$	2 ⇒ 1（右合同で $L$ を飽和するが $L$ は正規でない）
$L$ を飽和すること（同）	類が $\Sigma^{*}$ だけの右合同と $L=\{a^{k}b^{k}\}$	2 ⇒ 1（右合同で指数 $1$ だが $L$ は正規でない）
決定性（thm-mn-minimal-unique の 3）	$\{a\}$ 上の $L=\{a^{k}\mid k\ge1\}$ を受理する $2$ 状態の非決定性有限オートマトン 2 つ：$q_0\xrightarrow{a}q_1$、$q_1\xrightarrow{a}q_1$ と、$q_0\xrightarrow{a}q_0$、$q_0\xrightarrow{a}q_1$（どちらも受理状態は $q_1$）	状態数最小の受理器の一意性（$1$ 状態では受理できず、2 つは同型でない）
遷移がすべて定まっていること（同、thm-mn-main の状態数）	$\Sigma=\{a,b\}$、$L=\{a\}$。遷移を $q_0\xrightarrow{a}q_1$ だけにした $2$ 状態の部分的な DFA	状態数の最小値が $\equiv_L$ の指数（$[\varepsilon]$、$[a]$、$[b]$ の $3$）に等しいこと

補足

名称と文献

定理の名は、右合同による特徴づけを与えた A. Nerode（1958 年）と、合同関係による特徴づけを与えた J. Myhill（1957 年）による。thm-mn-main の 1 と 3 の同値と最小オートマトンの構成は SW10 Theorem 1.3（p. 27）、thm-mn-minimal-unique の 1・2 は同 Theorem 1.4（p. 28）、prop-mn-moore は同 Lemma 1.1（p. 29）、thm-mn-syntactic は同 Theorem 1.6（p. 33）にある。合同関係による形（$L$ を飽和する指数有限の合同が存在すれば正規、およびその逆）は BS81 Chapter III, §4 の Theorem 4.18（pp. 113–114）、構文的合同が $L$ を飽和する最大の合同であることは同 Lemma 4.20（p. 114）、構文モノイドの有限性による特徴づけは同 Theorem 4.22（p. 115）にあり、GvG23 Theorem 8.22（p. 241）は同じ特徴づけを分配束の双対性の立場から証明している。