Myhill-Nerodeの定理

言語が正規言語でないことを証明するのによく使われる Myhill-Nerode の定理について解説します。

直感的意味

任意の決定性有限オートマトン $M$ を考えましょう。このオートマトンに $011$ と $101$ を入力したときに、同じ状態に辿り着いたとします。

すると、この後、どのように文字列 $c_1 c_2 \cdots c_l \in \Sigma^*$ を入力しても、$011 c_1 c_2 \cdots c_l$ と $101 c_1 c_2 \cdots c_l$ は同じ状態にいるはずです。

ということは、受理されるかどうかも同じタイミングということで、$011 c_1 c_2 \cdots c_l \in L(M) \Leftrightarrow 101 c_1 c_2 \cdots c_l \in L(M)$ が成り立ちます。

これを一般化すると以下の補題が成り立ちます。

補題: 同じ状態に属する文字列は受理されるタイミングは同じ

オートマトンの状態 $v$ について、$$S_v = \{s \in \Sigma^* \mid s \text{ を } M \text{ に入力すると状態 } v \text{ に遷移する}\}$$ とおく。$s, t \in S_v$ であれば、任意の $u \in \Sigma^*$ について $su \in L(M) \Leftrightarrow tu \in L(M)$ が成り立つ。

決定性有限オートマトンの状態数は有限なので、これは以下の系を導きます。

系

言語 $L$ について、文字列集合 $\Sigma^*$ 上の同値関係 $\equiv_L$ を、$$s \equiv_L t \overset{\text{def}}{\Leftrightarrow} (\forall u \in \Sigma^*, su \in L \Leftrightarrow tu \in L)$$ と定義する。このとき、$L$ が正規ならば同値類は有限個になる。

$s \equiv_L t$ とはすなわち、$s, t$ の後にどのように文字列を入力しても受理されるかどうかは等しいということです。

これの逆も成り立つというのが Myhill-Nerode の定理です。

まずは準備として右不変とよばれる性質について証明しましょう。これはおおよそ、同じ状態に遷移した文字列はその後どのような文字列を入力しようと常に同じ状態に遷移し続けるということを表しています。

命題: 右不変性

文字列集合 $\Sigma^*$ 上の同値関係 $$s \equiv_L t \overset{\text{def}}{\Leftrightarrow} (\forall u \in \Sigma^*, su \in L \Leftrightarrow tu \in L)$$ は右不変である。すなわち、$s \equiv_L t$ であれば、任意の $u \in \Sigma^*$ に対して $su \equiv_L tu$ が成り立つ。

証明

$s \equiv_L t$ であれば、任意の $v \in \Sigma^*$ に対して、$$(su)v \in L \Leftrightarrow s(uv) \in L \Leftrightarrow t(uv) \in L \Leftrightarrow (tu)v \in L$$ が成り立つ。ただし、ふたつ目の $\Leftrightarrow$ は $s \equiv_L t$ より成立。よって、$su \equiv_L tu$。

次はいよいよ上述の系の逆の証明です。といっても、同値類を状態にもつオートマトンを構築するだけで証明になっています。

補題: 同値類が有限個であれば正規言語

文字列集合 $\Sigma^*$ 上の同値関係 $$s \equiv_L t \overset{\text{def}}{\Leftrightarrow} (\forall u \in \Sigma^*, su \in L \Leftrightarrow tu \in L)$$ により誘導される同値類が有限ならば、$L$ は正規言語である。

証明

決定性有限オートマトンを構築することで証明する。

状態集合 $Q$ を同値類全体の集合、初期状態 $q_0$ を $\varepsilon$ を含む同値類、受理状態 $F$ を言語 $L$ の要素からなる同値類全体の集合 $$F = \{q \in (\Sigma^* / \equiv_L) \mid q \cap L \neq \emptyset\}$$ とする。$\equiv_L$ の定義で $u = \varepsilon$ を考えると同値類 $q$ について $s \in q \cap L$ であれば他の要素 $t \in q$ についても $t \in L$ となるので、受理状態に対応する同値類には $L$ の要素しか含まないことに注意。状態 $q \in Q$ と文字 $c \in \Sigma$ について、$s$ を同値類 $q$ の代表元としたとき、遷移関数 $\delta(q, c)$ は、$sc$ を含む同値類と定義する。これは右不変性より well-defined。

このオートマトンに任意の文字列 $s \in \Sigma^*$ を入力すると、構成方法より明らかに、遷移先の状態は $s$ の属する同値類となる。受理集合の定義より、このオートマトンは言語 $L$ を認識する。よって $L$ は正規。

Myhill-Nerodeの定理

文字列集合 $\Sigma^*$ 上の同値関係 $$s \equiv_L t \overset{\text{def}}{\Leftrightarrow} (\forall u \in \Sigma^*, su \in L \Leftrightarrow tu \in L)$$ により誘導される同値類 $\Sigma^* / \equiv_L$ が有限であるときかつそのときのみ、$L$ は正規言語である。

また、おまけの嬉しい性質として、このオートマトンは最小であるという性質も持っています。

定理: オートマトンの最小性

正規言語 $L$ を認識するオートマトンの状態数は $\equiv_L$ の同値類の数以上である。すなわち、補題: 同値類が有限個であれば正規言語の証明で構築したオートマトンは、$L$ を認識するオートマトンの中で状態数が最小のものである。

証明

補題: 同じ状態に属する文字列は受理されるタイミングは同じより、オートマトンの状態 (v) について、$$S_v = \{s \in \Sigma^* \mid s \text{ を } M \text{ に入力すると状態 } v \text{ に遷移する}\}$$ とおくと $s, t \in S_v$ であれば $s \equiv_L t$ となる。よって、同値類の数はオートマトンの状態数以下となる。

Myhill-Nerodeの定理の使い方

Myhill-Nerode の定理は言語が正規言語ではないことを示すのに使われます。

言語が正規言語であると仮定し、同値類が有限個であることが導かれるが、ここから矛盾が生じるというのが典型的な流れです。

例を見てみましょう。

命題: 非正規言語の例

$A = \{0^n 1^n \mid n \ge 1\} = \{01, 0011, 000111, 00001111, \cdots\}$ は正規言語でない

証明

$A$ が正規言語であると仮定する。

Myhill-Nerode の定理より、文字列集合 $\Sigma^*$ 上の同値関係 $$s \equiv_A t \overset{\text{def}}{\Leftrightarrow} (\forall u \in \Sigma^*, su \in A \Leftrightarrow tu \in A)$$ により誘導される同値類は有限。

鳩の巣原理より、ある $i \neq j$ が存在して $0^i \equiv_A 0^j$ である。

しかし、$0^i 1^i \in A$ であるが、$0^j 1^i\ \not \in A$ である。これは同値性に反する。

よって、$A$ は正規言語ではない。

命題: 非正規言語の例

回文全体からなる言語 $A$ は正規言語でない

証明

$A$ が正規言語であると仮定する。

鳩の巣原理より、ある $i \neq j$ が存在して $0^i1 \equiv_A 0^j1$ である。

しかし、$0^i10^i \in A$ であるが、$0^j10^i \not \in A$ である。これは同値性に反する。

よって、$A$ は正規言語でない。

この例はどちらもポンピング補題の記事で紹介した非正規言語です。

ポンピング補題と Myhill-Nerode の定理はどちらも非正規性の証明に使われます。上の二例のように、同じ非正規性をどちらの補題を経由しても証明できることも多いです。どちらが使いやすいかはケースバイケースです。

まとめ

Myhill-Nerode の定理は言語が正規言語でないことを示すのに使われる
同値類が有限であることの必要性は、同じ状態に属する文字列はそのあと受理されるタイミングが同じであることから分かる
十分性は、同値類を状態としてオートマトンを構築すると証明できる
Myhill-Nerode の定理を使って非正規性を証明するときは、言語が正規言語であると仮定し、同値類が有限個であることが導かれるが、ここから矛盾が生じるというのが典型的な流れ