正規言語の反復補題
言語 L が正規言語であるとき、ある数(反復長)p > 0 について |w| ≥ p であるような L の任意の文字列 uwv を以下のように表現できる。
uwv = uxyzv
ここで文字列 x、y、z について |xy| ≤ p と |y| > 0 と次が成り立つ。
全ての i ≥ 0 の整数 i について uxyzv が L に属する。
このバージョンでは言語に要求する仕様がより厳密に表されているため、より多くの非正規言語を正規言語でないと証明できる。