文脈自由言語の反復補題

文脈自由言語の反復補題（ぶんみゃくじゆうげんごのはんぷくほだい、英: 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$ が文脈自由言語ではないことを証明する際によく使用される。これは、任意の長さの文字列 $s$ が $L$ に属しているものの、反復操作を行うと $L$ の外に出る文字列を生成することを示すことで証明される。

例えば、集合 $S\subset \mathbb {N}$ が無限であるが（無限の）等差数列を含まない場合、言語 $L=\{a^{n}:n\in S\}$ は文脈自由ではない。特に、$S$ が素数全体や平方数全体からなる言語は文脈自由言語ではない。

具体例として、言語 $L=\{a^{n}b^{n}c^{n}\mid n>0\}$ は、背理法で反復補題を使い文脈自由でないことが証明できる。まず、$L$ が文脈自由であると仮定する。反復補題によれば、言語 $L$ の反復長を表す整数 $p$ が存在する。このとき、文字列 $s=a^{p}b^{p}c^{p}$ を $L$ に属する文字列として考える。

反復補題によれば、文字列 $s$ は $s=uvwxy$ の形式で表現できる。

ここで、部分文字列 $u,v,w,x,y$ は以下の条件を満たす：

1. $|vx|\geq 1$
2. $|vwx|\leq p$
3. 任意の整数 $i\geq 0$ に対して $uv^{i}wx^{i}y\in L$

$s$ の選び方と $|vwx|\leq p$ という条件により、部分文字列 $vwx$ は高々2種類の異なる記号しか含まないことがわかる。このため、$vwx$ としてあり得る文字列は以下の5つに限定される：

1. $vwx=a^{j}$ （$j\leq p$）
2. $vwx=a^{j}b^{k}$ （$j+k\leq p$）
3. $vwx=b^{j}$ （$j\leq p$）
4. $vwx=b^{j}c^{k}$ （$j+k\leq p$）
5. $vwx=c^{j}$ （$j\leq p$）

各場合について、$uv^{i}wx^{i}y$ が $i\neq 1$ のとき各記号の数が等しくならないことを簡単に確認できる。例えば、$uv^{2}wx^{2}y$ は $a^{i}b^{i}c^{i}$ の形式にならないが、これは $L$ の定義に矛盾する。したがって、初めの仮定である「$L$ が文脈自由である」という主張は誤りであることが示された。

1960年、Scheinberg は補題の先駆けを用いて、言語 $L=\{a^{n}b^{n}a^{n}\mid n>0\}$ が文脈自由ではないことを証明した。

反復補題は、ある言語が文脈自由でないことを証明する上で便利なツールだが、文脈自由言語を完全に特徴づけるものではない。言語が反復補題の条件を満たさない場合、その言語は文脈自由ではないことが確立される。一方で、文脈自由ではないにもかかわらず、反復補題の条件を満たす言語も存在する。

例えば、以下の言語である： $L=\{b^{j}c^{k}d^{l}\mid j,k,l\in \mathbb {N} \}\cup \{a^{i}b^{j}c^{j}d^{j}\mid i,j\in \mathbb {N} ,i\geq 1\}$

この場合、文字列 $s=b^{j}c^{k}d^{l}$ に対して $j\geq 1$ の場合、$vwx$ を $b$ のみから構成し、また $s=a^{i}b^{j}c^{j}d^{j}$ に対して $vwx$ を $a$ のみから構成すれば、いずれの場合も反復された文字列は $L$ に属する。

参考文献

• 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.

関連項目

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