正規言語の反復補題
(2)の条件は繰り返しが先頭から p 文字以内から開始されることを意味する。x および z については特に制限はない。
反復補題の形式的表現を以下に示す。
( ∀ L ⊆ Σ ∗ ) ( regular ( L ) ⇒ ( ( ∃ p ≥ 1 ) ( ( ∀ w ∈ L ) ( ( | w | ≥ p ) ⇒ ( ( ∃ x , y , z ∈ Σ ∗ ) ( w = x y z ∧ ( | y | ≥ 1 ∧ | x y | ≤ p ∧ ( ∀ i ≥ 0 ) ( x y i z ∈ L ) ) ) ) ) ) ) ) {\displaystyle {\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}}}