うさぎでもわかるオートマトンと言語理論　第06羽　Myhill-Nerodeの定理・正則でない言語の証明法

こんにちは、ももやまです。

今までは決定性オートマトンを書いていくことを中心に説明していきました。

しかし今回は、いよいよみんなが(；´Д｀) うぅっ。。となる証明、具体的にはある言語が正則でないことを示す方法についてまとめていきたいと思います。

なんとか理解していきましょう……。

１．有限指数・右不変とは
- (1) 有限指数
- (2) 右不変
２．Myhill–Nerodeの定理
３．Myhill–Nerodeの定理と正則でない証明
- 例題1
- 解説1
４．正則な言語と正則でない言語の差
５．練習問題
- 練習1
- 練習2
６．練習問題の答え
- 解答1
- 解答2
６．さいごに

前回の記事（第05羽）はこちら！

www.momoyama-usagi.com

１．有限指数・右不変とは

マイヒル・ネロード(Myhill–Nerode)の定理で使われる有限指数、右不変についてまずは説明しておきましょう。

(1) 有限指数

$\Sigma^*$ 上の*1同値な関係 $R$ があるとします。この $R$ における同値類*2の数が有限であることを表します。

簡単に説明すると、（文字数が異なる）有限個の同じ文字列 $x$ を並べた関係 $x^i R x^j$ を有限指数といいます。
（ $i,j$ は文字数を表します。 $i \not = j$ , $i \gt j$ , $i \lt j$ などの条件を付け加えても有限指数と言えます。）

(2) 右不変

$\Sigma^*$ 上の二項関係 $R$ が\[
x \ R \ y \to 任意の \ z \in \Sigma^* \ に対し \ xz \ R \ yz
\]を満たすとき、右不変であると言います。

簡単に説明すると、二項関係が満たされている両者の文字列に同じものを加えても関係が成り立つのが右不変です。

２．Myhill–Nerodeの定理

では、本題のMyhill-Nerode（マイヒル・ネロード）の定理に入ります。

マイヒルネ・ロード（My昼寝・ロード）じゃないですよw（まぁ証明聞くと眠くなりますよねw）

Myhill-Nerodeの定理を下に示しておきます。

Myhill-Nerodeの定理

以下のその1、その2、その3はすべて同等である。

その1： $\Sigma^*$ 上の言語 $L$ が正則である

その2：言語 $L$ は有限指数かつ右不変な同値関係 $R$ による同値類の和で表される

その3： $\Sigma^*$ 上の2項関係 $\underset{L}{\equiv}$ は有限指数（かつ右不変）な同値関係となる。ただし $\underset{L}{\equiv}$ は\[
x \ \underset{L}{\equiv} \ y \Leftrightarrow 任意の \ z \in \Sigma^* \ に対し xz \in L \Leftrightarrow yz \in L \ または \ xz \notin L \Leftrightarrow yz \notin L
\]となる。
（ $xz \notin L \Leftrightarrow yz \notin L$ はあまり使われないので、またの部分以降は考えなくてもOK）

( ﾟдﾟ)ﾎﾟｶｰﾝってなった人が多いと思います。
でも大丈夫です。こんな定理なんだなーって思っておいてください。

３．Myhill–Nerodeの定理と正則でない証明

ここからが本題です。

ある言語 $L$ が正則（正規言語）であることを示したければ、言語 $L$ を受理する有限オートマトンを作成すればOKでしたね。

しかし、ある言語 $L$ が正則ではないことを示すために有限オートマトンが書けないことを示すのは難しいですよね。

そこで使われるのがMyhill-Nerodeの定理です。Myhill-Nerodeの定理と背理法をうまい具合に組み合わせることで言語 $L$ が正則でないことを示すことができちゃうのです。

試しに1問例題を出してみましょう。

例題1

$\Sigma = \{ a, b\}$ とする。このとき、言語\[
L = \left\{ a^i b^i \ \middle| \ \ i \in \mathbb{N} \ \right\}
\]が正則でないことを示したい。

以下の証明を穴埋めすることで証明を完成させなさい。

ただし、( 1 )・( 3 ) は適切な二項関係 $\underset{L}{\equiv}$ を用いた式を、( 2 ) は $i,j$ を用いた関係式を書くこと。

$\Sigma^*$ 上の二項関係 $\underset{L}{\equiv}$ をつぎのように定義する。\[
x \ \underset{L}{\equiv} \ y\underset{def}{\Leftrightarrow} \forall z \in \Sigma^* \ \ xz \in L \Leftrightarrow yz \in L
\]

$L$ が正則であると仮定すると、Myhill-Nerodeの定理より、 $\underset{L}{\equiv}$ は有限指数かつ右不変な同値関係となる。

(1) 有限指数であるから ( 1 ) となる自然数 $i,j$ が存在する。
（ただし ( 2 )である。）

(2) 右不変であるから ( 3 ) が成立する。

( 4 ) $\in L$ なので $\underset{L}{\equiv}$ の定義より ( 5 ) $\in L$ となる。

しかし、( 2 ) なので ( 5 ) $\notin L$ となる。

これは仮定に矛盾する。よって $L$ は正則でないことが示された。

解説1

解答

( 1 ) … $a^i \underset{L}{\equiv} a^j$
( 2 ) … $i \not = j$ （一応 $i \lt j$ , $i \gt j$ もOK）
( 3 ) … $a^i b^i \underset{L}{\equiv} a^j b^i$
( 4 ) … $a^i b^i$
( 5 ) … $a^j b^i$

証明解説

f:id:momoyama1192:20190905101729g:plain

流れとしては

Myhill-Nerodeを使うために $\underset{L}{\equiv}$ を定義
仮定より有限指数が成立するので $(文字)^i \underset{L}{\equiv} (文字)^j$ の関係を作る（ただし $i \not = j$ , $i \gt j$ , $i \lt j$ のいずれか）
仮定より右不変も成立するので2で作成した二項関係の両方に同じ文字列を連接することで二項関係の一方（左辺）を $L$ に属する言語、もう一方（右辺）を $L$ に属さない言語にし、仮定を矛盾させる

となります。

今回は $a^i b^i$ が正則でないことを示したいので、2項関係の一方を $a^i b^i$ が常に成り立つようにし、もう一方を $a^i b^i$ が常に満たさないようにします。

有限指数は、\[
a^i \underset{L}{\equiv} a^j
\]としましょう。左辺を $L$ に属する言語、右辺を $L$ に属さない言語にするためには、両辺に $b^i$ を連接させればよいことがわかる。よって右不変より\[
a^i b^i \underset{L}{\equiv} a^j b^i
\]も成立しますね。

ここで、 $a^i b^i \in L$ は明らかですよね。なので左辺は $L$ に属しています。また、 $i \not = j$ なのでどう頑張っても $a^j b^i \notin L$ になりますね。

Myhill-Nerodeの定理が成立すると仮定しているのに2項関係の左辺が $L$ に属し、右辺が属さないのは矛盾していますよね。

なので、仮定が誤りとなり、 $L$ は正則ではないことがわかります。

４．正則な言語と正則でない言語の差

では、正則な言語と正則でない言語にはどこに差があるのでしょうか。

基本的に無限に続く文字列を判定する際に無限の状態数（記憶数の上限がない）を記憶する必要があるような言語は正則ではありません。例えば、\[
L = \left\{ a^n b^n \ \middle| \ \ n \geqq 0 \right\}
\]は（上限がない） $a$ の数と $b$ の数を記憶させる必要がありますね。なので正則ではありませんね。ですが、\[
L = \left\{ a^n b^n \ \middle| \ \ n \leqq 1000 \right\}
\]とすると、 $n = 1001$ 以上の場合、絶対に受理されないので受理されるかどうかの判定は $n = 1000$ （有限）まですればよいので有限オートマトンで表すことができ、正則と言えます*3。

また、\[
L = \left\{ a^{2n} \ \middle| \ \ n\geqq 0 \right\}
\]も一見無限の記憶が必要に見えるのですが、どんな無限な数でも2で割ったあまりは0（偶数）か1（奇数）のどちらか（2状態）ですよね。なので正則です。

実際に正則かどうかを判定するのは慣れが必要だと思うので下に用意した練習問題で少し練習してみましょう。

５．練習問題

では、練習してみましょう。

練習1

つぎの(1)〜(4)の言語 $L_1$ , $L_2$ , $L_3$ , $L_4$ が正則ではないことを証明しなさい。

ただし、 $n$ は整数とする。

(1)

※ $|w|_a$ , $|w|_b$ はそれぞれ $a$ の語数、 $b$ の語数を表します。\[
L_1 = \left\{w \ \middle| \ \ w \in \Sigma^* , \ |w|_a > |w|_b \right\}
\]

(2)

$w^R$ は語 $w$ の反転を表します。\[
L_2 = \left\{w \ \middle| \ \ w \in \Sigma^* , \ w = w^R \right\}
\]

(3)\[
L_3 = \left\{wxw \ \middle| \ \ w \in \Sigma^* , \ x \in \Sigma^+ \right\}
\]

(4)\[
L_4 = \left\{x a^n b^n \ \middle| \ \ x \in \Sigma^* , n \geqq 1 \right\}
\]

練習2

次の $L_1$ 〜 $L_5$ の中から正則な言語を2つ選び、番号で答えなさい。

※指示がない限り $m,n$ は0以上の整数とする。また、 $w^R$ は語（文字列） $w$ の反転を、 $|w|_a$ は $w$ に含まれる

\[
L_1 = \left\{a^m b^n b^m \ \middle| \ \ m,n \geqq 0 \ \right\} \\
L_2 = \left\{a^m b^n b^n \ \middle| \ \ m,n \geqq 0 \ \right\} \\
L_3 = \left\{ww^R \ \middle| \ \ w \in \Sigma^* ,\ \ |w| \leqq 1000 \ \right\} \\
L_4 = \left\{w \ \middle| \ \ w \in \Sigma^* ,\ \ -3 \geqq |w|_a - |w|_b \geqq 3 \ \right\} \\
L_5 = \left\{a^n w b^n \ \middle| \ \ w \in \Sigma^* ,\ \ |w| \leqq 1000 \right\}
\]

６．練習問題の答え

解答1

(1)

f:id:momoyama1192:20190905101734g:plain

(2)

f:id:momoyama1192:20190905101738g:plain

(3)

f:id:momoyama1192:20190905101744g:plain

(4)

f:id:momoyama1192:20190905101749g:plain

解答2

解答： $L_2$ , $L_3$

それぞれの解説

言語 $L_1$

$a^m b^n b^m$ （ $b$ の数が $a$ の数以上なら正則）なので無限に続く文字列が受理するかどうか判定するために（上限数がない） $a$ の数を記憶させる必要があるため、正則ではない。

（簡潔な証明）

有限指数より、 $a^i \underset{L}{\equiv} a^j$ となる $i,j$ （ただし $i \gt j$ ）が存在、右不変より $a^i b^i \underset{L}{\equiv} a^j b^i$ となる。

$a^i b^i \in L$ だが $a^j b^i \notin L$ より正則でない。

言語 $L_2$

$a^m b^n b^n$ ということは $a^m b^{2n}$ と同等。

つまり、 $a^m$ のあとに $b^{2n}$ を連接するような言語である。

$a^m$ （ $a$ だけで構成されるような文字列を受理する言語）はもちろん正則、 $b^{2n}$ （ $b$ だけが偶数文字並ぶような文字列を受理する言語）も正則なので、当然連接したものも正則となる。

言語 $L_3$

$|w| \lt 1000$ がポイント

$w$ が1000文字以下と決められているので、 $w$ 1001文字以上の文字列の判定は不要（絶対受理しないため）

なので1000文字分（有限）の記憶で受理するかどうかの判定が可能なため、正則である。

言語 $L_4$

$-3 \geqq |w|_a - |w|_b \geqq 3$ がポイント。

$|w|_a$ の文字数、 $|w|_b$ の文字数をそれぞれ記憶し、判定しないと受理可能かどうかは調べられない。無限の記憶必要でなので正則ではない。

（簡潔な証明）

有限指数より、 $a^i \underset{L}{\equiv} a^j$ となる $i,j$ （ただし $i \gt j$ ）が存在、右不変より $a^i b^{i+3} \underset{L}{\equiv} a^j b^{i+3}$ となる。

$a^i b^{i+3} \in L$ だが $a^j b^{i+3} \notin L$ より正則でない。

言語 $L_5$

$|w| \leqq 1000$ がポイント。
ただし、範囲が有限だからといって正則とすぐには判定しないように。

$a^n w b^n$ ということは $w$ が1000文字以下なら無条件に受理、しかし判定したい文字列が1000文字以上だからといって無条件に受理しないとは限らず、始点と終点の $a$ の文字数と $b$ の文字数が一致すれば受理する。そのため受理するかどうかを判定するために（上限数がない）始点と終点の $a$ の文字、 $b$ の文字の数を記憶させる必要がある。よって正則ではない。

６．さいごに

今回はオートマトンと言語理論において、正則ではない言語であること、つまり有限オートマトンが書けないことを証明するための道具に使えるMyhill-Nerodeの定理についてまとめました。

今後は正則な言語かどうかの判定を行い、正則の場合は決定性オートマトンの記述、正則ではない場合はMyhill-Nerodeの定理における証明をする必要があります。しかし、最初はなかなか難しいと思うので次の次の記事で練習問題を持ってこようと思います。

次回は文脈自由文法について軽く説明します。

*1:任意の文字列上のと思ってください。

*2:同値なものを集めた集合

*3: $n \geqq 1001$ のときは強制的に非受理にすればOK。なので無限の記憶は不要。

工業大学生ももやまのうさぎ塾

うさぎでもわかるをモットーに大学レベルの数学・情報科目をわかりやすく解説！