正規言語の反復補題とは？わかりやすく解説

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

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

形式的定義

$L$

この 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$

[1]

正規言語の反復補題とは？ わかりやすく解説