正規言語のポンピング補題

形式言語理論において、正規言語のポンピング補題は、すべての正規言語の本質的な性質を記述する補題である。非公式には、正規言語の十分に長い文字列はすべてポンピング（つまり、文字列の中央部分を任意の回数繰り返す）して、その言語の一部でもある新しい文字列を生成できるというものである。ポンピング補題は、特定の言語が正規言語ではないことを証明するために、その言語にその性質がないことを示すのに役立つ。

具体的には、ポンピング補題は、任意の正規言語 に対して、少なくとも長さ である 内の任意の文字列が 3 つの部分文字列 と( 、空でない )に分割でき、その文字列も に含まれるような定数が存在することを述べています。0 回以上繰り返すプロセスは、「ポンピング」として知られています。さらに、ポンピング補題は の長さが最大 ​​になることを保証し、したがって、目的の特性を持つ 「小さな」部分文字列を提供します。${\displaystyle L}$${\displaystyle p}$${\displaystyle w}$${\displaystyle L}$${\displaystyle p}$${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$${\displaystyle w=xyz}$${\displaystyle y}$${\displaystyle xz,xyz,xyyz,xyyyz,...}$${\displaystyle L}$${\displaystyle y}$${\displaystyle xy}$${\displaystyle p}$${\displaystyle xy}$

文字列の数が有限の言語は、がの最大文字列長に 1 を加えた値に等しいことによって、ポンピング補題を空虚に満たします。 そうすることで、 のゼロ文字列の長さは より長くなります。 ${\displaystyle p}$${\displaystyle L}$${\displaystyle L}$${\displaystyle p}$

ポンピング補題は1959年にマイケル・ラビンとダナ・スコットによって初めて証明され、 ^[1]その後まもなく、 1961年にイェホシュア・バーヒレル、ミカ・A・パールズ、イーライ・シャミールによって文脈自由言語に対するポンピング補題の簡略化として再発見されました。^{[2] [3]}

を正規言語とします。すると、のみに依存する整数が存在し、 内の少なくとも長さ(は「ポンピング長」と呼ばれます)のすべての^文字列は と書き表すことができます(つまり、 は3 つの部分文字列に分割できます)。これは次の条件を満たします。 ${\displaystyle L}$${\displaystyle p\geq 1}$${\displaystyle L}$${\displaystyle w}$${\displaystyle L}$${\displaystyle p}$${\displaystyle p}$${\displaystyle w=xyz}$${\displaystyle w}$

1. ${\displaystyle |y|\geq 1}$
2. ${\displaystyle |xy|\leq p}$
3. ${\displaystyle (\forall n\geq 0)(xy^{n}z\in L)}$

${\displaystyle y}$は、ポンピング可能な部分文字列です（任意の回数削除または繰り返すことができ、結果の文字列は常に 内にあります）。 (1)は、ポンピングするループの長さが少なくとも 1 でなければならないこと、つまり空の文字列であってはならないことを意味します。 (2) は、ループが最初の文字の範囲内で発生しなければならないことを意味します。 は、（(1) と (2) の結論）より小さくなければなりませんが、それ以外に、とに制限はありません。 ${\displaystyle L}$${\displaystyle y}$${\displaystyle p}$${\displaystyle |x|}$${\displaystyle p}$${\displaystyle x}$${\displaystyle z}$

簡単に言えば、任意の正規言語 について、十分に長い文字列( 内) は 3 つの部分に分割できます。つまり、のすべての文字列も に含まれるようになります。 ${\displaystyle L}$${\displaystyle w}$${\displaystyle L}$${\displaystyle w=xyz}$${\displaystyle xy^{n}z}$${\displaystyle n\geq 0}$${\displaystyle L}$

以下はポンピング補題の正式な表現です。

${\displaystyle {\begin{array}{l}\forall L\subseteq \Sigma ^{*},{\mbox{regular}}(L)\implies \\\quad \exists p\geq 1,\forall w\in L,|w|\geq p\implies \\\qquad \exists x,y,z\in \Sigma ^{*},(w=xyz)\land (|y|\geq 1)\land (|xy|\leq p)\land (\forall n\geq 0,xy^{n}z\in L)\end{array}}}$

ポンピング補題は、特定の言語が非正規であることを証明するためによく使用されます。背理法による証明は、ポンピング補題で概説されている特性を欠く言語の文字列 (必要な長さの文字列) を示すことで構成される場合があります。

例:アルファベット上の言語は、次のように非正規であることが示されます。 ${\displaystyle L=\{a^{n}b^{n}:n\geq 0\}}$${\displaystyle \Sigma =\{a,b\}}$

1. 、およびを、上記のポンピング補題の正式な記述で使用されているものとしましょう。${\displaystyle w,x,y,z}$${\displaystyle n}$
2. 補題によって要求される定数が存在すると仮定します。${\displaystyle p}$
3. の が で与えられるものとします。これは より長い文字列です。${\displaystyle w}$${\displaystyle L}$${\displaystyle w=a^{p}b^{p}}$${\displaystyle p}$
4. ポンピング補題により、任意のに対してとなるような、 およびによる分解が存在しなければなりません。${\displaystyle w=xyz}$${\displaystyle |xy|\leq p}$${\displaystyle |y|\geq 1}$${\displaystyle xy^{i}z}$${\displaystyle L}$${\displaystyle i\geq 0}$
5. なので、文字列は のインスタンスのみで構成されます。${\displaystyle |xy|\leq p}$${\displaystyle y}$${\displaystyle a}$
6. なぜなら、この文書には文字 が少なくとも 1 つ含まれているからです。${\displaystyle |y|\geq 1}$${\displaystyle a}$
7. を にパンピングすると、のインスタンスがいくつか追加されましたが、 のインスタンスは追加されていないため、文字 よりも文字 のインスタンスが多い単語が生成されます。${\displaystyle y}$${\displaystyle xy^{2}z}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$${\displaystyle b}$
8. したがって、はポンピング補題に矛盾する には該当しません。${\displaystyle xy^{2}z}$${\displaystyle L}$
9. したがって、正規にはなり得ません。${\displaystyle L}$

バランスのとれた（つまり、適切にネストされた）括弧の言語が正規ではないことの証明も、同じ考え方に従います。 が与えられた場合、 個以上の左括弧で始まるバランスのとれた括弧の文字列が存在するため、 はすべて左括弧で構成されます。 を繰り返すと、左括弧と右括弧の数が同じではない文字列が生成され、バランスが取れなくなります。 ${\displaystyle p}$${\displaystyle p}$${\displaystyle y}$${\displaystyle y}$

すべての正規言語には、その言語を受け入れる有限状態オートマトン(FSA)が存在します。このような FSA の状態数がカウントされ、その数がポンピング長 として使用されます。長さ 以上の文字列について、を開始状態とし、 を文字列が発行されるときに次に訪れる状態のシーケンスとします。FSA には状態 しかないため、この一連の訪問状態の中には繰り返される状態が少なくとも 1 つ存在する必要があります。このような状態について を記述します。マシンが状態 の最初の遭遇から状態 の 2 番目の遭遇まで遷移する部分は、何らかの文字列と一致します。この文字列は補題で と呼ばれ、マシンは部分がない文字列や、文字列が何回も繰り返された文字列と一致するため、補題の条件は満たされます。 ${\displaystyle p}$${\displaystyle p}$${\displaystyle q_{0}}$${\displaystyle q_{1},...,q_{p}}$${\displaystyle p}$${\displaystyle p}$${\displaystyle p+1}$${\displaystyle q_{s}}$${\displaystyle q_{s}}$${\displaystyle q_{s}}$${\displaystyle y}$${\displaystyle y}$${\displaystyle y}$

たとえば、次の画像は FSA を示しています。

FSA は文字列 abcd を受け入れます。この文字列の長さは状態の数と同じかそれ以上であるため、状態数は 4 です (したがって、マシンがabcd をスキャンするために通過する状態の総数は5 になります)。ピジョンホール原理によれば、開始状態と次に訪れる 4 つの状態の間には、少なくとも 1 つの繰り返される状態が存在する必要があります。この例では、 のみが繰り返される状態です。部分文字列bc は、マシンを状態 で始まり状態 で終わる遷移に導くため、その部分が繰り返されても FSA は受け入れることができ、文字列abcbcdが生成されます。あるいは、bc部分を削除しても FSA は受け入れることができ、文字列adが生成されます。ポンピング補題では、文字列abcdは部分a、部分bc、および部分dに分割されます。 ${\displaystyle q_{1}}$${\displaystyle q_{1}}$${\displaystyle q_{1}}$${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$

余談ですが、与えられた文字列が、与えられた非決定性有限オートマトンによって、どの状態も繰り返して訪れることなく受け入れられるかどうかを確認する問題は、 NP困難です。

言語が正規言語である場合、その言語に含まれるすべての文字列が次のように表記されるよう な数（ポンピング長）が存在する。${\displaystyle L}$${\displaystyle p\geq 1}$${\displaystyle uwv}$${\displaystyle L}$${\displaystyle |w|\geq p}$

${\displaystyle uwv=uxyzv}$

文字 列、およびとなり、${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$${\displaystyle |xy|\leq p}$${\displaystyle |y|\geq 1}$

${\displaystyle uxy^{i}zv}$は任意の整数に対して成り立つ。^[5]${\displaystyle L}$${\displaystyle i\geq 0}$

このことから、上記の標準バージョンは、との両方が空の文字列である特殊なケースに従います。 ${\displaystyle u}$${\displaystyle v}$

一般バージョンでは言語に対してより厳しい要件が課されるため、より多くの言語の非正規性を証明するために使用できます。

ポンピング レンマは、すべての正規言語が上記の条件を満たすと述べていますが、このステートメントの逆は真ではありません。つまり、これらの条件を満たす言語は、非正規である可能性があります。言い換えると、ポンピング レンマの元のバージョンと一般的なバージョンはどちらも、言語が正規であるための 必要条件は示していますが、十分条件ではありません。

たとえば、次の言語を考えてみましょう。

${\displaystyle {\begin{matrix}L&=&\{uvwxy:u,y\in \{0,1,2,3\}^{*};v,w,x\in \{0,1,2,3\}\land (v=w\lor v=x\lor x=w)\}\\&&\cup \ \{w:w\in \{0,1,2,3\}^{*}\land {\text{正確に }}{\tfrac {1}{7}}{\text{ }}w{\text{ の文字の }\}\end{matrix}}}$。

つまり、 には、重複文字を含む長さ 3 の部分文字列を持つアルファベット上のすべての文字列と、文字列の文字の 1/7 が 3 であるこのアルファベット上のすべての文字列が含まれます。この言語は正規ではありませんが、 で「ポンプ」することができます。文字列sの長さが少なくとも 5 であるとします。アルファベットには 4 文字しかないため、文字列の最初の 5 文字のうち少なくとも 2 文字は重複している必要があります。それらは最大 3 文字で区切られます。 ${\displaystyle L}$${\displaystyle \{0,1,2,3\}}$${\displaystyle p=5}$

• 重複する文字が 0 文字または 1 文字で区切られている場合は、文字列内の他の 2 つの文字のいずれかをポンプします。これにより、重複を含む部分文字列には影響しません。
• 重複する文字が 2 文字または 3 文字で区切られている場合は、それらを区切っている文字のうち 2 つをポンプします。下方向または上方向にポンプすると、重複する文字が 2 つ含まれるサイズ 3 の部分文字列が作成されます。
• の 2 番目の条件は、が正則でないことを保証します。文字列 を考えます。この文字列は、のときにちょうど内であり、したがってマイヒル-ネローデの定理により、 は正則ではありません。${\displaystyle L}$${\displaystyle L}$${\displaystyle (013)^{3m}(012)^{i}}$${\displaystyle L}$${\displaystyle i=4m}$${\displaystyle L}$

マイヒル・ネローデ定理は、正規言語を正確に特徴付けるテストを提供します。言語が正規であることを証明するための一般的な方法は、その言語の有限状態マシンまたは正規表現を構築することです。

• オグデンの補題
• 文脈自由言語のポンピング補題
• 正規木言語のポンピング補題

• ローソン、マーク V. (2004)。有限オートマトン。チャップマン＆ホール/CRC。ISBN 978-1-58488-255-8.ZBL1086.68074  。​
• Sipser, Michael (1997)。「1.4: 非正規言語」。計算理論入門。PWS Publishing。pp. 77–83。ISBN 978-0-534-94728-6.ZBL1169.68300。 ​
• ホップクロフト、ジョン E. ;ウルマン、ジェフリー D. (1979)。オートマトン理論、言語、計算入門。マサチューセッツ州レディング: Addison-Wesley Publishing。ISBN 978-0-201-02988-8.ZBL0426.68001  。​ （第3章を参照）
• Bakhadyr Khoussainov、Anil Nerode ( 2012年 12 月 6 日)。オートマトン理論とその応用。Springer Science & Business Media。ISBN 978-1-4612-0171-7。