文脈自由言語のポンピング補題

コンピュータサイエンス、特に形式言語理論において、文脈自由言語のポンピング補題は、バー・ヒレル補題とも呼ばれ、^[1]全ての文脈自由言語に共通する性質を与え、正規言語のポンピング補題を一般化する補題である。

ポンピング補題は、特定の言語が文脈自由ではないという背理法による反証を構築するために使用できます。逆に、ポンピング補題だけでは言語が文脈自由であることを保証するには不十分であり、オグデンの補題や交換補題など、他の必要条件があります。

言語が文脈自由である場合、ある整数（「ポンピング長」と呼ばれる）^[2]が存在し、その中の任意の文字列の長さがまたはそれ以上の記号（つまり）は次のように記述できる。 ${\displaystyle L}$${\displaystyle p\geq 1}$${\displaystyle s}$${\displaystyle L}$${\displaystyle p}$${\displaystyle |s|\geq p}$

${\displaystyle s=uvwxy}$

部分文字列 とがあり、 ${\displaystyle u,v,w,x}$${\displaystyle y}$

1. 、${\displaystyle |vx|\geq 1}$

2. 、そして${\displaystyle |vwx|\leq p}$

3.全員に対して。${\displaystyle uv^{n}wx^{n}y\in L}$${\displaystyle n\geq 0}$

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

${\displaystyle {\begin{array}{l}(\forall L\subseteq \Sigma ^{*})\\\quad ({\mbox{context free}}(L)\Rightarrow \\\quad ((\exists p\geq 1)((\forall s\in L)((|s|\geq p)\Rightarrow \\\quad ((\exists u,v,w,x,y\in \Sigma ^{*})(s=uvwxy\land |vx|\geq 1\land |vwx|\leq p\land (\forall n\geq 0)(uv^{n}wx^{n}y\in L)))))))\end{array}}}$

文脈自由言語のポンピング補題 (この記事の残りの部分では単に「ポンピング補題」と呼びます) は、すべての文脈自由言語が必ず持つ特性を記述します。

プロパティは、言語内の少なくとも長さ のすべての文字列の特性です。ここで、 は、文脈自由言語間で異なる 定数（ポンピング長と呼ばれる）です。${\displaystyle p}$${\displaystyle p}$

少なくともその言語にある 長さの文字列であるとします。${\displaystyle s}$${\displaystyle p}$

ポンピング補題は、 を5 つの部分文字列 に分割できることを述べています。ここで、は空でなく、 の長さは最大 です。したがって、 で とを同じ回数 ( )繰り返すと、言語に含まれる文字列が生成されます。 を 0 回繰り返すと、文字列からと が削除されるため、便利なことがよくあります。と の追加のコピーで「ポンピング」するこのプロセスから、ポンピング補題にその名前が付けられています。 ${\displaystyle s}$${\displaystyle s=uvwxy}$${\displaystyle vx}$${\displaystyle vwx}$${\displaystyle p}$${\displaystyle v}$${\displaystyle x}$${\displaystyle n}$${\displaystyle s}$${\displaystyle v}$${\displaystyle x}$${\displaystyle s}$${\displaystyle v}$${\displaystyle x}$

有限言語(正規言語であり、したがって文脈自由言語)は、最大文字列長に1 を加えた値を持つことにより、ポンピング補題に自明に従います。この長さの文字列は存在しないため、ポンピング補題は違反されません。 ${\displaystyle p}$${\displaystyle L}$

ポンピング補題は、任意の長さの文字列sがL内にあり、 L の外部に文字列を生成せずに「ポンピング」できないことを示すことによって、特定の言語Lが非文脈自由であることを証明するためによく使用されます。

たとえば、が無限であるが、（無限）等差数列を含まない場合、 は文脈自由ではありません。特に、素数も平方数も文脈自由ではありません。 ${\displaystyle S\subset \mathbb {N} }$${\displaystyle L=\{a^{n}:n\in S\}}$

たとえば、言語 が文脈自由でないことは、背理法による証明でポンピング補題を使用することで示せます。まず、L が文脈自由であると仮定します。ポンピング補題により、言語Lのポンピング長である整数p が存在します。 L内の文字列 を考えてみましょう。ポンピング補題によれば、s はの形式で記述でき、u、v、w、x、y は部分文字列であり、すべての整数 に対して、、 となります。 sの選択と という事実から、部分文字列vwx には 2 つ以上の異なるシンボルを含められないことが容易にわかります。つまり、 vwxには 5 つの可能性があります。 ${\displaystyle L=\{a^{n}b^{n}c^{n}|n>0\}}$${\displaystyle s=a^{p}b^{p}c^{p}}$${\displaystyle s=uvwxy}$${\displaystyle |vx|\geq 1}$${\displaystyle |vwx|\leq p}$${\displaystyle uv^{i}wx^{i}y\in L}$${\displaystyle i\geq 0}$${\displaystyle |vwx|\leq p}$

1. ${\displaystyle vwx=a^{j}}$一部の人にとっては。${\displaystyle j\leq p}$
2. ${\displaystyle vwx=a^{j}b^{k}}$あるjとkに対して${\displaystyle j+k\leq p}$
3. ${\displaystyle vwx=b^{j}}$一部の人にとっては。${\displaystyle j\leq p}$
4. ${\displaystyle vwx=b^{j}c^{k}}$あるjとkに対して、となります。${\displaystyle j+k\leq p}$
5. ${\displaystyle vwx=c^{j}}$一部の人にとっては。${\displaystyle j\leq p}$

それぞれの場合について、には任意の の各文字が同数含まれないことは簡単に確認できます。したがって、は という形式ではありません。これはLの定義と矛盾します。したがって、 Lが文脈自由であるという当初の仮定は誤りであるに違いありません。 ${\displaystyle uv^{i}wx^{i}y}$${\displaystyle i\neq 1}$${\displaystyle uv^{2}wx^{2}y}$${\displaystyle a^{i}b^{i}c^{i}}$

1960年に、シャインバーグはポンピング補題の前身を用いて、が文脈自由ではないことを証明した。^[3]${\displaystyle L=\{a^{n}b^{n}a^{n}|n>0\}}$

ポンピング補題は、与えられた言語が文脈自由ではないことを証明するのにしばしば役立つツールであるが、文脈自由言語の完全な特徴付けを与えるものではない。言語がポンピング補題によって与えられた条件を満たさない場合、その言語は文脈自由ではないと証明される。一方、文脈自由ではないが、ポンピング補題によって与えられた条件を満たす言語もある。例えば、

${\displaystyle L=\{b^{j}c^{k}d^{l}|j,k,l\in \mathbb {N} \}\cup \{a^{i}b^{j }c^{j}d^{j}|i,j\in \mathbb {N} ,i\geq 1\}}$

s = b ^j c ^k d ^l（例えばj ≥ 1）の場合、vwx はbのみで構成されることを選択し、s = a ⁱ b ^j c ^j d ^jの場合、 vwx はaのみで構成されることを選択します。どちらの場合も、すべてのポンピングされたストリングはLに残ります。^[4]

• バーヒレル、Y. ;ミカ・パールズ;イーライ・シャミール(1961)。 「単純な句構造文法の形式的性質について」。Zeitschrift für Phonetik、Sprachwissenschaft、および Kommunikationsforschung。14 (2): 143–172。— 再版: Y. Bar-Hillel (1964)。言語と情報:その理論と応用に関する選集。Addison-Wesley論理学シリーズ。Addison-Wesley。pp. 116–150。ISBN 0201003732. OCLC  783543642.
• マイケル・シプサー（1997年）。計算理論入門。PWS出版。ISBN 0-534-94728-X。セクション1.4: 非正規言語、pp. 77–83。セクション2.3: 非文脈自由言語、pp. 115–119。