このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

［参照用 記事］

ポンプの補題とその使い方： 回文の例

雑記／備忘

ポンプの補題の証明は比較的簡単ですが、言っていることの解釈や使い方は難しいです。

内容：

なんかオカシイ

インターネット上で、ポンプの補題と回文について説明しているスライドに出会いました*1。回文とは、「シンブンシ」とか「タケヤブヤケタ」のように、逆向きに読んでも同じになる文字列のことです。件のスライドは「文字列が回文か否かを、正規表現を使って判断できない」ことを示していて、結論自体は正しいのですが、途中の議論がだいぶアヤシイ（つうか間違ってます）。

でも、「しょうがないかな」という気もします。回文の全体が正規言語にならないことを示すにはポンプの補題〈pumping lemma〉を使います。このポンプの補題は、その表現が複雑で、取り扱いが難しいのです。

ポンプの補題

ポンプの補題を日本語で書いてみます。

  • Lが無限正規言語であれば、次の性質を満たす整数 p ≧ 1 が存在する。
    • 長さがp以上の任意のLの語wは、次の性質を満たす分解 w = xyz を持つ。
      1. xyの長さはp以下
      2. yの長さは1以上
      3. 任意の非負整数（0も入れる）iに対して、xyiz はLの語である。ここで、yiは語yをi回繰り返したもの。

一読して何を言ってるのかを理解するのは難しいですよね。でも、証明は意外に簡単で、鳩の巣原理〈pigeonhole principle〉を使います。

ポンプの補題の記述を日本語で正確に扱うのは困難そうなので、後で論理式に直します。ここでは、ポンプの補題の（おそらく）語源だと思われる事実を指摘します。諸々の条件のもとで、語wを w = xyz とうまいこと分解すると、xz, xyz, xyyz, xyyyz, xyyyyz, ... がすべてLの語になります。

*2

この様子が、xとzのあいだに井戸があり、ポンプのひと押しごとにyを汲み出しては貯めていくように見えるからポンプの補題なのでしょう、たぶん（よく知らんけど）。

正規言語

記号を並べたものを語〈word〉と呼びます。語を構成している個々の記号〈symbol〉は、集合Σの要素だとします。ギリシャ大文字シグマを使うのは形式言語理論の習慣です（おそらく、symbolのSから）。集合Σをアルファベット〈alphabet〉と呼び、ここでは有限だと仮定します。Σの要素を文字〈character〉とか字〈letter〉と呼ぶこともあり、そのときは語を文字列〈string〉とも呼びます。ときに、Σの要素を語と呼び、語を文〈sentence〉と呼ぶこともあります。

Σの記号から構成される語の全体をΣ*と表します。Σ*の部分集合を言語〈language〉と呼びます。形式言語理論の文脈での「言語」は今定義したものであり、通常の意味の「言語」とは違います。言語学的／哲学的に考えないでください*3。Lが（アルファベットΣ上の）言語だとは、LがΣ*のベキ集合Pow(Σ*)の要素であること L∈Pow(Σ*) 、それだけのこと、それ以上でも以下でもありません。

さて、Σ上の言語Lが正規言語〈regular language〉であることには、同値ないくつかの定義があります。

一番馴染みやすいのは、「正規表現で定義できる言語が正規言語である」でしょう。他に、クリーネ代数を使った定義、論理系を使った定義、半環上の行列代数を使った定義、トレース付きモノイド圏を使った定義などもあります。正規表現（とオートマトン）の基本的なことは次の記事にあります。

ポンプの補題 再度

ポンプの補題〈pumping lemma〉は、正規言語の性質を述べているものです。ただし、有限な正規言語（有限言語はすべて正規言語）では成立しませんたいして意味を持ちません。正規言語Lが集合として無限集合のときだけポンプの補題が成立しますを考えることにします。[追記]「… では成立しません。」という言い方は不適切でした。この記事のコメント欄と記事最後の追記を参照。[/追記]ポンプの補題は次のように書けます。

  • Regular(L) ∧ Infinite(L) ⇒ Pump(L)

Pump(L)は、Lがポンプの補題の性質を満たすことです。Pump(L)を日本語で「Lはポンプする」と言うことにします。上記命題を日本語で言えば：

  • Lが正規言語で かつ Lが無限集合 ならば Lはポンプする

ポンプの補題は、与えられた言語Lが正規言語でないことを証明する際に使われます。このとき、「背理法を用いて、Lを正規言語だと仮定して矛盾を導く」とかよく言いますが、そう考える必要はありません。与えられた言語Lが、単に「ポンプしない」ことを示せばいいだけです。

先のポンプの補題の対偶をとってみます。'¬'は否定（not）を表す論理記号です。

  • ¬Pump(L) ⇒ ¬(Regular(L) ∧ Infinite(L))

'⇒'の右側にド・モルガンの法則を適用すれば、

  • ¬Pump(L) ⇒ ¬Regular(L) ∨ ¬Infinite(L)

通常、与えられる言語は無限言語だと分かっていますから、Infinite(L)は仮定されています。Infinite(L) と ¬Regular(L) ∨ ¬Infinite(L) からは ¬Regular(L) が出ます。

がんばって証明
     ：
     ：
--------------
   ¬Pump(L)   [ポンプの補題] ¬Pump(L) ⇒ ¬Regular(L) ∨ ¬Infinite(L)
------------------------------------------------------------------------[1]
[最初からの仮定] Infinite(L)   ¬Regular(L) ∨ ¬Infinite(L)
-------------------------------------------------------------[2]
              ¬Regular(L)

推論[1]は、「A, A⇒B よって B」というモーダスポネンンスです。推論[2]もモーダスポネンスです。¬A∨¬B ≡ ¬B∨¬A ≡ B⇒¬A なので、「B, B⇒¬A よって ¬A」という形です。

あるいは、論理式に関して、'⇒'越しに式を移動する“移項の原理”*4を使って、

  • ¬Pump(L) ⇒ ¬Regular(L) ∨ ¬Infinite(L)

から

  • ¬Pump(L) ∧ Infinite(L) ⇒ ¬Regular(L)

も言える、と思ってもいいです。

結局、無限言語Lに関して、Lがポンプしないことを示せば、Lは正規言語でないことになります。あえて背理法とか言うこともないでしょう。

「ポンプする」とは

与えられた言語Lがポンプしないことを示せば、Lが正規言語でないと言えます。ポンプしない、すなわち ¬Pump(L) を正確に書いてみましょう。そのためには、まずは Pump(L) を正確に書いて、それを否定します。

Pump(L)は次の形をしています。

  • Pump(L) ≡ ∃p≧1.Pump(L, p)

ここで、'≡'は論理式として同値な（同じとみなしてよい）ことです。'≡'の右側にも'Pump'が出てきますが、これは'≡'の左側の'Pump'とは別物です。引数の数〈number of arguments〉が違うんで区別できるだろうと、サボって同じ記号を流用（オーバーロード）してます。∃p≧1.Pump(L, p) で存在が保証される整数pを、Lのポンプ長〈pumping length〉といいます。Pump(L, p)を、「Lは（ポンプ長）pでポンプする」と言えば、

  • Lがポンプする とは Lがpでポンプするようなポンプ長pが存在する

ですね。さらに「Lはpでポンプする」を分解していきます。|w|は語wの長さです。

  • Pump(L, p) ≡ ∀w∈L.(|w|≧p ⇒ pump(L, w, p))

これは、Lの語wが長さp以上なら、「（語として）ポンプする」ことです。小文字の'pump'は、「Lの語wは、（ポンプ長）pでポンプする」と読むことにして、これは語wにフォーカスした言明になっています。その pump(L, w, p) は、

  • pump(L, w, p) ≡ ∃x, y, z.(w = xyz ∧ |xy|≦p ∧ |y|≧1 ∧ ∀i≧0.(xyiz∈L))

x, y, z はΣ*の要素ですが、x, y, z∈Σ* の'∈Σ*'は省略しています。どんな x, y, z が存在するのかというと：

  1. x, y, z をこの順で連接〈concatenate〉するとwになる。
  2. xyの長さはp以下。
  3. yの長さは1以上。
  4. 任意の非負整数iに対して、xyiz がLの語になる。

はい、これで（ポンプの補題の意味での）「ポンプする」の記述はオシマイです。全部展開して書くと：

  • ∃p≧1.(∀w∈L.(|w|≧p ⇒ (∃x, y, z.(w = xyz ∧ |xy|≦p ∧ |y|≧1 ∧ ∀i≧0.(xyiz∈L)))

「ポンプしない」とは

「Lがポンプしない」は、¬Pump(L) を求めればいいので、前節の分解した定義に従って順に否定していきましょう。

  • ¬Pump(L) ≡ ¬∃p≧1.Pump(L, p)

存在記号に関するド・モルガンの法則により、

  • ¬Pump(L) ≡ ∀p≧1.¬Pump(L, p)

¬Pump(L, p) は、

  • ¬Pump(L, p) ≡ ¬∀w∈L.(|w|≧p ⇒ pump(L, w, p))

全称記号に関するド・モルガンの法則により、

  • ¬Pump(L, p) ≡ ∃w∈L.(|w|≧p∧¬pump(L, w, p))

ここで、含意 A⇒B の否定が A∧¬B であることを使っています。さらに、¬pump(L, w, p) は、

  • ¬pump(L, w, p) ≡ ¬∃x, y, z.(w = xyz ∧ |xy|≦p ∧ |y|≧1 ∧ ∀i≧0.(xyiz∈L))

また存在記号に関するド・モルガンの法則により、

  • ¬pump(L, w, p) ≡ ∀x, y, z.(w = xyz ∧ |xy|≦p ∧ |y|≧1 ⇒ ¬∀i≧0.(xyiz∈L))

ここでは、A∧B∧C∧D の否定が A∧B∧C ⇒ ¬D となっています。これは次のような変形の結果です。

    ¬(A∧B∧C∧D)
 ≡ ¬((A∧B∧C)∧D)
 ≡ ¬(A∧B∧C)∨¬D
 ≡ (A∧B∧C) ⇒ ¬D

¬∀i≧0.(xyiz∈L) に、また全称記号に関するド・モルガンの法則を適用して、

  • ¬∀i≧0.(xyiz∈L) ≡ ∃i≧0.(xyiz !∈ L)

'!∈'は「所属しない」の意味です。今までの変形をまとめると：

  • ∀p≧1.(∃w∈L.(|w|≧p ∧ ∀x, y, z.(w = xyz ∧ |xy|≦p ∧ |y|≧1 ⇒ ∃i≧0.(xyiz !∈ L))))

日本語にしてみると：

  • 1以上の任意の整数pに対して、次の性質を満たすLの語wが存在する。
    • wは長さp以上。
    • Lの任意の語x, y, zに対して、次が成立する。
      • w = xyz であり かつ xyの長さがp以下 かつ yの長さが1以上 ならば 次の性質を持つ。
        • ある非負整数iが存在して、xyizはLの語ではない。

「存在する／存在して」が入っているので、「ポンプしない」ことを示すには、条件を満たす語wと非負整数iを具体的に見つける必要があります。

回文の全体は正規言語ではない

では、表記の命題をポンプの補題を使って証明しましょう。まずは注意事項： アルファベットΣが単一の記号、例えばaしか含まないとき、Σ = {a} 上の語はすべて回文になります。(Σ上の回文の全体) = Σ* = (正規表現 a* で定義される言語) なので、回文の全体は正規言語です。これは例外です。

Σは2個以上の要素を持つとします。要素は何でもいいので、Σ = {0, 1} とします（3個以上の要素があっても話は同じ）。Σ上の回文〈palindrome〉の全体をP（大文字だよ）とします。Pがポンプしないことを示します。

p（小文字だよ）を1以上の任意の整数とします。このpに対して、回文（Pの語）を次のように定義します。

  • w = 0p10p

ここで、0pは0をp個並べたものです。例えば（あくまで例えば） p = 3 ならば、w = 0001000 です。wは明らかに回文です。

wを w = xyz かつ |xy|≦p かつ |y|≧1 であるように分解します。|xy| ≦ p であることから、xyは0の並びになります。yは1個以上の0の並びです。xの長さをn、yの長さをmとしましょう。すると、

  • xy = 0n+m （0 ≦ n ≦ p - 1, 1 ≦ m ≦ p, 1 ≦ n + m ≦ p）
  • x = 0n
  • y = 0m

と書けます。ここで、xy0 = x とすると、長さは n となり、(p - 1)個以下の0の並びです。したがって xy0z は、「(p - 1)個以下の0の並び 1 p個の0の並び」となり回文ではありません。（iを十分大きくしても回文でなくなります。）

以上で、w = 0p10p という回文（Pの語）と、i = 0 という非負整数が見つかって、「w = xyz かつ |xy|≦p かつ |y|≧1 であるような分解」をどう取ろうが、xy0zはPの語ではないように出来ることが分かりました。つまり、回文の全体Pはポンプしません。

ポンプの補題が「ポンプしない無限言語は正規言語ではない」と主張しているので、回文の全体Pは正規言語ではありません。もちろん、Pを正規表現で定義できるはずはありません。

おわりに

命題が複雑になると、その否定や対偶を作るのはけっこう大変になります。しかし、否定や対偶は頻繁に使う論理的操作なので、正確に変形できないと困ることがあります。入れ子になった存在記号や全称記号はド・モルガン法則で否定しましょう。そもそも、入れ子になった存在記号や全称記号の解釈が難しいので、正確を期すには自然言語だけでなく論理式で書いたほうがいいと思います。


[追記]コメント欄で、はいさんからご指摘があったように、Regular(L) ∧ Infinite(L) ⇒ Pump(L) ではなくて、Regular(L) ⇒ Pump(L) でも命題は成立するので、Infinite(L) を明示的に付ける必要はありません。Lが有限言語の場合、pをどの語の長さよりも大きく取ると、|w|≧p ⇒ pump(L, w, p) の |w|≧p が常に偽になり、pump(L, w, p) の真偽に関わらずこの含意命題が成立し、有限言語でも適当な整数pにおいてポンプの補題の性質を満たすことになります。

というわけで、Infinite(L)は不要です。でも、事実上無限言語でしかポンプの補題を使わないので、一種の適用条件としてInfinite(L)を置いといても害はないと思います。本文内の記述はそのままです。[/追記]

*1:間違いを具体的に指摘するのが目的ではないので、URL参照はしません。

*2:画像： https://ja.wikipedia.org/wiki/手押しポンプ#/media/File:WellPump.JPG 神戸市市東灘区石屋川の公園にある井戸ポンプ

*3:形式言語理論／数理言語学も言語学の一部門と考えるなら、今は数理的なアプローチしか考えない、ということ。

*4:厳密には、論理式を古典論理のシーケントの形に書いたときに、移項の原理が機能します。