正規言語の反復補題

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

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

1. 形式的定義
--------

を正規言語とすると、 のみに依存する次のような反復長 が存在する。 に属する長さ 以上の任意の文字列 は と書ける。ここで、 、、 は次の条件を満たす。

全ての について、//y// は反復される部分文字列。|//y//| は文字列 //y// の長さを意味し、の条件は //y// が少なくとも長さを持つ空でない文字列であることを意味している。の条件は繰り返しが先頭から //p// 文字以内から開始されることを意味する。//x// および //z// については特に制限はない。

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

2. 解説
-----

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

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

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

3. 利用
-----

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

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

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

//y//が//aibj //であるとすると、//y//を繰り返すと//a//と//b//が交互に出現することになり、//anbn//という//L//の定義に反することになる。

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

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

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

4. 証明
-----

この証明法は、全ての正規言語にその言語を受理する有限状態機械  が存在するという事実を利用している。正規言語が有限であれば、十分に大きいに対して が常に偽になるため、反復補題が真であることは自明である。

正規言語が無限の場合、その言語を受理する最小 FSA が存在しなければならない。FSA の状態数は有限であるから、その個数を反復長 //p// とする。文字列長が //p// 以上の場合、反復される状態が少なくとも1つ存在する。状態 //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 が対応する。もちろん、他の当てはめ方もあるが、|//xy//| ≤ //p// を満たしていない。

5. 反復補題の不十分性
------------

反復補題は、ある言語が正規言語であるための十分条件ではないことに注意されたい。つまり、正規言語以外でもこの反復補題が成り立つことがある。言語 //L// について反復補題が成り立たない場合、//L// が正規言語でないことがわかる。しかし、反復補題が成り立ったとしても、//L// が必ず正規言語であるとは言えない。例えば、言語 //{uuRv : u,v {0,1}+}//は正規言語ではないが、//p// = 4で反復可能である。//u// の長さが 1 であれば、|//v//| ≥ 2 であり、//v// の先頭の文字を //y// とすればよい。さもなくば、//u// の先頭文字を //y// とする。正規言語のより実用的な判定方法についてはマイヒル-ネローデの定理を参照されたい。ある言語が正規言語であることを証明する典型的な方法は、その言語を受理する有限オートマトンか正規表現を構築することである。

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

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

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

全ての //i// ≥ 0 の整数 //i// について //uxyizv// が //L// に属する。このバージョンでは言語に要求する仕様がより厳密に表されているため、より多くの非正規言語を正規言語でないと証明できる。

7. 参考文献
-------

author = Michael Sipser 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. ////

de:Pumping-Lemma#Reguläre Sprachen