正規言語の反復補題

正規言語の反復補題（英: pumping lemma for regular languages）とは、全ての正規言語が持つ属性を与える補題である。反復補題一般の具体例の一つである。その主たる用法は、ある言語が正規言語でないことを証明することである。

この反復補題は1961年に Y. Bar-Hillel、M. Perles、E. Shamir によって最初に示された^[1]。

形式的定義

$L$ を正規言語とすると、 $L$ のみに依存する次のような反復長 $p\geq 1$ が存在する。 $L$ に属する長さ $p$ 以上の任意の文字列 $w$ は $w=xyz$ と書ける（つまり、 $w$ は3つの部分文字列に分けられる）。ここで、 $x$ 、 $y$ 、 $z$ は次の条件を満たす。

$|y|\geq 1$
$|xy|\leq p$
全ての $i\geq 0$ について、 $xy^{i}z\in L$

y は反復される部分文字列（0回を含む任意の回数繰り返され、結果として生成される文字列も L に属する）。|y| は文字列 y の長さを意味し、(1)の条件は y が少なくとも長さを持つ空でない文字列であることを意味している。(2)の条件は繰り返しが先頭から p 文字以内から開始されることを意味する。x および z については特に制限はない。

反復補題の形式的表現を以下に示す。

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

解説

正規言語の反復補題（以下、単に反復補題と略記）は、全ての正規言語が持つと保証されている属性を表している。より正確に言えば、正規言語に属する文字列の持つ属性を表している。ここで扱う正規言語の文字列は長さ p 以上（p は定数。形式的定義での p と同じ）で、これを反復長（pumping length）と呼ぶ。反復長は個々の正規言語によって異なる。s が長さ p 以上のある文字列で、正規言語 L に含まれるものとする。反復補題によれば、何らかの方法で s を3つに分割して $s=xyz$ としたとき、その（空ではない）中央部分 yを（0回を含む）任意回数繰り返した文字列も L に含まれる。このように文字列の一部の複製を追加していくことを「反復; pumping」と呼び、そのため反復補題と呼ばれている。さらに、反復補題は xy の長さが最大でも p となるような s の分割があることを保証している。

反復補題は、ある言語が正規言語ではないことを証明するのに使われる（補題と呼ばれるのはそのためである）。その場合、反復補題に示される属性をその言語に属する文字列が持たないことを示せばよい。

正規言語が有限の場合、つまりその正規言語に含まれる文字列の長さに上限がある場合、 $p$ をその正規言語に含まれる最大の文字列長より大きいと仮定すると、反復補題の形式的表現の論理式は常に真となる。つまり反復補題が意味するところは、正規言語は有限か、無限であれば、任意の文字列の中間に表れる文字列に対する反復（任意回数の繰り返し）を、その正規言語が許容するということであり、いずれの場合でもないものは、正規言語ではないということである。

利用

反復補題を使ってある言語が正規言語でないことを示すには、背理法を用いる。ある言語 L を正規言語と仮定し、L に属する全文字列が正規言語の反復補題に従うものとする。そして、具体例によって反復補題の属性を持たない文字列があることを示し、仮定が間違っていることを導き出して、L が正規言語ではないことを示す。すなわち、文字列 w ∈ L と整数 i の組合せで反復補題に反するものを探す。

この反復補題を使えば、例えばアルファベット Σ = {a, b} を使った言語 L = {aⁿbⁿ : n ≥ 0} が正規言語でないことを証明できる。この場合、補題に出てくる w, x, y, z, p, i をその言語に当てはめる。まず、w = a^pb^p とする。この w を w = xyz、|xy| ≤ p、|y| ≥ 1 となるよう分解し、i ≥ 0 のとき xyⁱz が L に属するかどうかを確認する。

どのように当てはめるかということについては、3通りの方法が考えられる。

yがaⁱb^j (0 ≤ i ≤ n, 0 ≤ j ≤ n )であるとすると、yを繰り返すとaとbが交互に出現することになり、aⁿbⁿというLの定義に反することになる。

次に、|xy|=p かつ |z|=p としたとき、xy は w の前半、すなわち p 個の a に対応する。|y| ≥ 1 なので、y は1個以上の a で構成される。すると、xy²z は a の個数と b の個数が違うことになり、L の定義に反する（i ≠ 1 について常に矛盾が生じる）。この場合、矛盾が導かれたので、反復補題が成り立たないことがわかる。

もうひとつのパターンは、|xy|=p=|w| かつ |z|=0 の場合、つまりx=aⁿ、y=bⁿ, z= $\epsilon$ の場合であるが、これも同様に、xy²z は a の個数と b の個数が違うことになり、L の定義に反する。従って、Lに属する文字列をどのように分割しても、反復補題から矛盾が導かれ、L が正規言語であるという仮定に誤りがあることになる。従って、L が正規言語でないことが証明される。

括弧が正しく対応している言語（'(' と ')' が同じ個数出現し、最初が '(' で最後が ')' となる言語）も同様の考え方で正規言語でないことが証明できる。ある p について、左括弧が先頭から p 個以上続く文字列では、y には左括弧しか含まれない。従って y を反復すると、左括弧だけが多い文字列となって、定義に反することになる。

証明

この証明法は、全ての正規言語にその言語を受理する有限状態機械 (FSA) が存在するという事実を利用している。正規言語が有限であれば、十分に大きい $p$ に対して $|w|\geq p$ が常に偽になるため、反復補題が真であることは自明である（ $|w|\geq p$ が偽であれば、 $(|w|\geq p)\Rightarrow ((\exists x,y,z\in \Sigma ^{*})(w=xyz\land (|y|\geq 1\land |xy|\leq p\land (\forall i\geq 0)(xy^{i}z\in L))))$ という論理式全体は、 $\Rightarrow$ の右側の式の真偽値によらず真になる。そのため、十分に大きい $p$ に対して、この条件式は真となるため、正規言語が有限であれば、 $\exists p\geq 1$ という条件を常に満たすことになる）。

正規言語が無限の場合、その言語を受理する最小 FSA が存在しなければならない。FSA の状態数は有限であるから、その個数を反復長 p とする。文字列長が p 以上の場合、反復される状態が少なくとも1つ存在する（この状態を S とする）。状態 S から S への遷移は何らかの文字列に対応する。この文字列を反復補題における y とすれば、y を含まない文字列（繰り返し部分に相当する遷移をしない場合）も、y を繰り返す文字列もFSAで受理されるため、反復補題が成り立つことがわかる。

例を見てみればより理解しやすいだろう。以下の状態遷移図は、ある FSA を示している。

この FSA は文字列 abcbcd を受理する。この文字列は状態数より多くの文字からなるので、状態を繰り返していることがわかる。この例では q1 と q2 が繰り返される状態である。文字列 abcbcd の部分文字列 bcbc は、状態 q1 から始まって状態 q1 に戻る遷移で形成されるので、この文字列部分はFSAによる繰り返しが可能であり、abcbcbcbcd のような文字列も受理される。また、その遷移のループを通らない文字列 ad も同様に受理される。反復補題に当てはめると、文字列 abcbcd は、x に a、y に bc、z に bcd が対応する。もちろん、他の当てはめ方もある（y に bcbc を対応させる）が、|xy| ≤ p を満たしていない。

反復補題の不十分性

反復補題は、ある言語が正規言語であるための十分条件ではないことに注意されたい。つまり、正規言語以外でもこの反復補題が成り立つことがある。言語 L について反復補題が成り立たない場合、L が正規言語でないことがわかる。しかし、反復補題が成り立ったとしても、L が必ず正規言語であるとは言えない。例えば、言語 {uu^Rv : u,v $\in$ {0,1}⁺}（アルファベット {0,1} で構成される回文形式の空でない文字列に別の文字列が付属したもの）は正規言語ではないが、p = 4（w=uu^Rv の長さが 4 以上の場合）で反復可能である。u の長さが 1 であれば、|v| ≥ 2 であり、v の先頭の文字を y とすればよい。さもなくば、u の先頭文字を y とする（k ≥ 2 のときの y^k は空でない回文 yy で始まる文字列を構成し、残りを v と見なせば、この言語に属することになる）。正規言語のより実用的な判定方法についてはマイヒル-ネローデの定理を参照されたい。ある言語が正規言語であることを証明する典型的な方法は、その言語を受理する有限オートマトンか正規表現を構築することである。

一般化された「正規言語の反復補題」

言語 L が正規言語であるとき、ある数（反復長）p > 0 について |w| ≥ p であるような L の任意の文字列 uwv を以下のように表現できる。

uwv = uxyzv

ここで文字列 x、y、z について |xy| ≤ p と |y| > 0 と次が成り立つ。

全ての i ≥ 0 の整数 i について uxyⁱzv が L に属する。

このバージョンでは言語に要求する仕様がより厳密に表されているため、より多くの非正規言語を正規言語でないと証明できる。

参考文献

^ Y. Bar-Hillel, M. Perles, E. Shamir, "On formal properties of simple phrase structure grammars", Zeitschrift für Phonetik, Sprachweissenshaft und Kommunikationsforschung 14 (1961) pp. 143-172.

Michael Sipser (1997年). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X Section 1.4: Nonregular Languages, pp.77–83.
John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 3.)

[1] Y. Bar-Hillel, M. Perles, E. Shamir, "On formal properties of simple phrase structure grammars", Zeitschrift für Phonetik, Sprachweissenshaft und Kommunikationsforschung 14 (1961) pp. 143-172.

[1]