文脈自由言語の反復補題

文脈自由言語の反復補題（ぶんみゃくじゆうげんごのはんぷくほだい、英: Pumping lemma for context-free languages）は、全ての文脈自由言語が持つ属性を与える反復補題である。Bar-Hillelの補題や、uvwxy定理とも呼ばれる。その主たる用法は、ある言語が文脈自由言語でないことを証明することである。

文脈自由言語の反復補題は、任意の文脈自由言語でない言語が文脈自由でないことを証明するのに使えるわけではない。場合によってはより汎用化されたオグデンの補題を使う必要がある。

形式的定義

任意の文脈自由言語 L に対して，（反復長 (pumping length) と呼ばれる）ある正の整数 p > 0 が存在し、L 内の |w| ≥ p となる任意の文字列 w を以下のように表すことができる：

w = uvxyz

このとき、文字列 u、v、x、y、z について |vxy| ≤ p、|vy| ≥ 1、そして以下が成り立つ。

全ての0以上の整数 i ≥ 0 について uv ⁱxy ⁱz が L に含まれる。

なお、文字列 a と b があるとき ab はその連結した文字列を表し、|a| は a の長さを表す。また、aⁱ は a を i 回反復した文字列を表す。

解説

文脈自由言語の反復補題（以下、単に反復補題と略記）は、全ての文脈自由言語が持つと保証されている属性を表している。その属性は、当該言語に含まれる長さ p 以上の全ての文字列について成り立つ。ここで、p は定数であり、反復長と呼ばれ、個々の文脈自由言語によって異なる。s が長さ p 以上の文字列とする。反復補題によれば、s は5つの部分文字列 $s=uvxyz$ に分けられ、vy は空でない文字列で、vxy の長さは最大で p であり、s の中の v と y に相当する部分を任意の同じ回数繰り返して生成される文字列も同じ言語に含まれる（ゼロ回繰り返す場合も含まれ、その場合 v と y に相当する部分がない文字列 uxz となる）。このような v と y の複製を追加していくことを「反復; pumping」と呼び、そのため反復補題と呼ばれている。

反復補題で言語が文脈自由でないことを証明するには、その言語に含まれる長さ p 以上の文字列 s が上述の属性を持たないことを示せばよい。つまり、反復によってその言語に含まれない文字列が生成されることを示す。

利用例

文脈自由言語の反復補題は、ある言語が文脈自由言語でないことを示すのに使われる。ここでは、例として、言語 L = {a^jb^jc^j, j>0} が文脈自由でないことを示す。

1. L が文脈自由であると仮定する
   1. 条件:
      1. | vxy | ≤ p。つまり、中央部分は長すぎない。
      2. vy ≠ ε（空の文字列）。v と y は「反復」対象なので、この条件は反復すべき文字列の少なくとも一方が空文字列でないことを意味する。
      3. 全ての i ≥ 0 について、uvⁱxyⁱz が L に含まれる。すなわち、2つの文字列 v と y は 0 回を含む任意の回数反復され、それによって生成された文字列も L に含まれる。
2. w ∈ L かつ | w | > p であるような文字列 w について、w = uvxyz と表され、| vxy | ≤ p が成り立つとする。
3. ここで、p より大きい値 j を選ぶ。
4. そして、文字列 vxy が文字列 a^jb^jc^j に含まれるとした場合、a の右端の文字と c の左端の文字の間には j 個の文字があるため、vxy には最大でも2種類の文字しか含まれないことになる。
   1. 例えば、vxy は全て a か、全て b か、全て c か、あるいは a と b で構成されるか、b と c で構成される。
      1. 従って、文字列 vxy は2種類を越える文字種を含むことはできないが、反復補題によれば空文字列も許されない。そのため少なくとも1つの文字を必ず含む。
5. ここで「反復」を開始する。
   1. uvxyz は L に含まれるので、uv²xy²z も L に含まれるはずである。v と y が共に空であることは許されないので、| uv²xy²z | > | uvxyz | であり、文字が追加されているはずである。
   2. しかし、v と y は全ての（3種類の）文字種を含まないので、各文字種の文字が同じ個数になるように文字を追加できない。つまり、反復による文字追加で生成される文字列と言語 L の本来の定義に矛盾が生じる。従って、uv²xy²z は L には含まれない。
6. このような矛盾が生じたことから、L が文脈自由であるという最初の前提が偽であることがわかる。  KJ
   

関連項目

• 正規言語の反復補題
• オグデンの補題
• 形式言語

参考文献

• Michael Sipser (1997年). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X  Section 1.4: Nonregular Languages, pp.77–83. Section 2.3: Non-context-free Languages, pp.115–119.