正規言語の反復補題
概要
正規言語の反復補題（pumping lemma for regular languages）とは、正規言語 $L$ に対して正の整数 $p$ があり、長さ $p$ 以上の $L$ の元 $w$ はどれも、$|y|\ge1$、$|xy|\le p$ で、すべての $m\ge0$ について $xy^mz\in L$ となる分解 $w=xyz$ をもつという定理である。$L$ を受理する決定性有限オートマトンが長い文字列を読むと同じ状態を 2 度通ることから従い、$p$ には状態数がとれる。言語が正規でないことを示す標準的な道具だが、正規であるための十分条件ではなく、結論を満たすのに正規でない言語がある。
正規言語の反復補題（pumping lemma for regular languages）は、正規言語の十分長い文字列には、先頭の近くに「何回繰り返しても、取り除いても言語から外れない」部分がある、という主張である。有限オートマトンは有限個の状態しかもたないので、長い文字列を読むと同じ状態を 2 度通り、その間に読んだ部分はいくらでも繰り返せる。これが補題の内容のすべてである。
反復補題は、言語が正規でないことを示す標準的な道具である。ただし正規であるための必要条件にすぎず、補題の条件を満たすのに正規でない言語がある。この記事では、補題とその少し強い形を証明し、正規でないことを示す使い方、補題から従う無限性の判定、補題の逆が成り立たない例を述べる。
定義と主張
以下、$\Sigma$ は有限のアルファベット、$\Sigma^{*}$ はその上の文字列全体、$\varepsilon$ は空語、$|w|$ は文字列 $w$ の長さ、$y^m$ は $y$ を $m$ 回並べた文字列（$y^0=\varepsilon$）を表す。決定性有限オートマトン（DFA）$\mathcal A=(Q,\Sigma,\delta,q_0,F)$ と、遷移関数の文字列への拡張 $\delta(q,w)$ は 有限オートマトン の記事の定義「非決定性有限オートマトンと決定性有限オートマトン」による。$\delta(q,uv)=\delta(\delta(q,u),v)$ が成り立つ。正規言語 の記事の定理「Kleene の定理」と 有限オートマトン の記事の命題「部分集合構成」により、正規言語 $L$ にはそれを受理する DFA がある。
$L\subset\Sigma^{*}$ を正規言語とする。このとき正の整数 $p$ があって、$|w|\ge p$ を満たす任意の $w\in L$ は、次の 3 条件を満たす分解 $w=xyz$ をもつ。
- $|y|\ge1$
- $|xy|\le p$
- すべての整数 $m\ge0$ について $xy^mz\in L$
$p$ としては、$L$ を受理する DFA の状態数がとれる。この $p$ を 反復定数 という。
$L$ を受理する DFA $\mathcal A=(Q,\Sigma,\delta,q_0,F)$ をとり、$p:=|Q|$ とする。$w=a_1a_2\cdots a_n\in L$（$a_i\in\Sigma$、$n\ge p$）について、$q_i:=\delta(q_0,a_1\cdots a_i)$（$0\le i\le n$）とおく。$q_0,q_1,\dots,q_p$ は $p+1$ 個の状態の並びで $Q$ の元は $p$ 個なので、鳩の巣原理 により $q_i=q_j$ となる $0\le i< j\le p$ がある。
$x:=a_1\cdots a_i$、$y:=a_{i+1}\cdots a_j$、$z:=a_{j+1}\cdots a_n$ とおくと、$|y|=j-i\ge1$、$|xy|=j\le p$ である。$\delta(q_i,y)=q_j=q_i$ なので、$m$ に関する帰納法で $\delta(q_i,y^m)=q_i$ がすべての $m\ge0$ で成り立つ。よって
$$
\delta(q_0,xy^mz)=\delta(\delta(\delta(q_0,x),y^m),z)=\delta(q_i,z)=\delta(q_j,z)=\delta(q_0,w)\in F
$$
であり、$xy^mz\in L$ である。$\square$
$\Sigma=\{0,1\}$ 上で、$1$ の個数が $3$ の倍数である文字列の言語 $L$ は、状態 $q_0,q_1,q_2$（それまでに読んだ $1$ の個数を $3$ で割った余り）をもつ DFA で受理される。$0$ を読んでも状態は変わらず、$1$ を読むと $q_k$ から $q_{k+1}$（添字は $3$ を法とする）へ移り、受理状態は $q_0$ だけである。$p=3$ として $w=0111\in L$ を読むと、状態は $q_0,q_0,q_1,q_2,q_0$ と進み、最初の 2 つが一致するので $x=\varepsilon$、$y=0$、$z=111$ が補題の分解になる。$w=1110$ なら状態は $q_0,q_1,q_2,q_0$ と進むので $y=111$ で、$1^{3m}0$ はどれも $L$ に属する。$y$ は「状態を一周させる部分」であり、何周しても、一周もしなくても行き先は変わらない。
反復定数 $p$ は DFA の状態数にとれるが、それより小さい値で結論が成り立つこともある。たとえば有限言語では、元の長さの最大値より大きい $p$ をとれば、$|w|\ge p$ となる元がないので結論は空に成り立つ。
量化の順序は「ある $p$ があって、すべての長い $w$ について、ある分解があって、すべての $m$ について」である。正規でないことを示すには、この否定、つまり「どの $p$ についても、ある $w\in L$（$|w|\ge p$）があって、条件 1・2 を満たすどの分解 $xyz$ についても、ある $m$ で $xy^mz\notin L$」を示す。$p$ と分解は相手が選び、$w$ と $m$ はこちらが選ぶ遊びと見ることができる。
証明では状態の重複を先頭の $p+1$ 個の中で探したが、どこで探してもよい。これから次の形が得られる。
$L$ を $p$ 状態の DFA が受理する言語とする。$uvw'\in L$、$|v|\ge p$ なら、$v=xyz$ で $|y|\ge1$、$|xy|\le p$、かつすべての $m\ge0$ について $uxy^mzw'\in L$ となるものがある。
$v=b_1\cdots b_k$（$k\ge p$）とし、$r_i:=\delta(q_0,ub_1\cdots b_i)$（$0\le i\le p$）とおくと、鳩の巣原理により $r_i=r_j$（$i< j\le p$）がある。$x:=b_1\cdots b_i$、$y:=b_{i+1}\cdots b_j$、$z:=b_{j+1}\cdots b_k$ とすれば、prf-pumping-regular と同じ計算で $\delta(q_0,uxy^mzw')=\delta(q_0,uvw')\in F$ である。$\square$
使い方
次の言語はどれも正規でない。どれも、正規だと仮定して thm-pumping-regular の $p$ をとり、矛盾を導く。
- $L_1=\{0^n1^n\mid n\ge0\}$。$w=0^p1^p$ をとる。$|xy|\le p$ なので $y=0^r$（$r\ge1$）であり、$xz=0^{p-r}1^p\notin L_1$。
- $L_2=\{1^n\mid n\text{ は素数}\}$。素数 $n\ge p+2$ をとり、$w=1^n$ とする。$y=1^k$（$1\le k\le p$）として $m=n-k$ とすると、$|xy^mz|=n-k+(n-k)k=(n-k)(k+1)$ で、$n-k\ge2$、$k+1\ge2$ なので合成数であり、$xy^mz\notin L_2$。
- $L_3=\{0^i1^j\mid i>j\ge0\}$。$w=0^{p+1}1^p$ をとる。$y=0^r$（$r\ge1$）で、$m=0$ とすると $xz=0^{p+1-r}1^p$ の $0$ の個数は $p$ 以下で、$xz\notin L_3$。
- $L_4=\{1^{n^2}\mid n\ge0\}$。$w=1^{p^2}$ をとる。$1\le|y|\le p$ なので $p^2<|xy^2z|=p^2+|y|\le p^2+p<(p+1)^2$ であり、$|xy^2z|$ は平方数でなく、$xy^2z\notin L_4$。
3 では文字列を増やす向き（$m\ge2$）では矛盾が出ず、取り除く向き（$m=0$）を使う。文字列 $w$ の選び方も重要である。$\{vv\mid v\in\{0,1\}^{*}\}$ について $w=0^{2p}$ を選ぶと、相手は長さ $2$ の $y=00$ をとれて矛盾が出ないが、$w=0^p10^p1$ を選べば $y=0^r$ となり、$xy^2z=0^{p+r}10^p1$ は $vv$ の形にならない（長さが奇数か、前半が $0$ だけで後半が $1$ を含む）。MSm24 §2.9.1（pp. 70–73）にこれらの例がある。
thm-pumping-regular-anywhere は thm-pumping-regular より強く、反復させる部分の位置を指定したいときに使う。後で見る言語 $F$（prop-pumping-regular-converse-fails）は thm-pumping-regular の結論を満たすので、そのままでは正規でないことを示せない。しかし $F$ が $p$ 状態の DFA で受理されるとして、$ab^pc^p\in F$ の中央の $b^p$ を $v$ にとると、$y=b^r$（$r\ge1$）を取り除いた $ab^{p-r}c^p$ が $F$ に属さないので、$F$ が正規でないことが直接分かる。
無限性の判定
反復補題から、正規言語が無限集合かどうかは有限個の文字列を調べれば分かる。
$L$ を $p$ 状態の DFA が受理する言語とする。$L$ が無限集合であることと、$p\le|w|< 2p$ を満たす $w\in L$ があることは同値である。
そのような $w$ があれば、thm-pumping-regular の分解で $xy^mz$（$m\ge0$）は長さ $|w|+(m-1)|y|$ が相異なる $L$ の元なので、$L$ は無限集合である。逆に $L$ が無限集合なら、長さ $p$ 以上の元があるので、そのうち最短のもの $w$ をとる。$|w|\ge2p$ とすると、分解 $w=xyz$ について $xz\in L$ で、$|xz|=|w|-|y|\ge|w|-p\ge p$、$|xz|<|w|$ となり最短性に反する。よって $p\le|w|< 2p$ である。$\square$
調べる文字列は有限個なので、DFA が与えられれば $L$ が無限かどうかは有限回の計算で判定できる。
文字が 1 種類のときは、同じ鳩の巣原理の議論から正規言語が完全に分かる。$A\subset\mathbb N$ が 最終的に周期的 であるとは、整数 $N\ge0$、$d\ge1$ があって、$n\ge N$ なら「$n\in A\iff n+d\in A$」となることをいう。
$\Sigma=\{1\}$ とする。$L\subset\Sigma^{*}$ が正規であることと、長さの集合 $A:=\{n\mid1^n\in L\}$ が最終的に周期的であることは同値である。
$L$ を受理する DFA をとり、$s_n:=\delta(q_0,1^n)$ とおく。状態は有限個なので $s_N=s_{N+d}$（$d\ge1$）となる $N,d$ がある。$s_{n+1}=\delta(s_n,1)$ なので、$n\ge N$ なら帰納法で $s_{n+d}=s_n$ であり、$n\in A\iff s_n\in F\iff s_{n+d}\in F\iff n+d\in A$ である。
逆に $A$ が $N,d$ で最終的に周期的なら、状態 $0,1,\dots,N+d-1$、初期状態 $0$、遷移 $k\mapsto k+1$（$k< N+d-1$）と $N+d-1\mapsto N$、受理状態 $\{k\mid k\in A\}$ の DFA を作る。$1^n$ を読んだ後の状態は、$n< N+d$ なら $n$、$n\ge N$ なら $N\le k< N+d$ かつ $k\equiv n\pmod d$ となる $k$ で、周期性からどちらでも「$k\in A\iff n\in A$」なので、この DFA は $L$ を受理する。$\square$
最終的に周期的な無限集合では、$N$ 以上の元 $n$ が 1 つあれば $n,n+d,n+2d,\dots$ がすべて元なので、隣り合う元の間隔は $N$ より先では $d$ 以下である。素数の集合は、$n!+2,\dots,n!+n$ がどれも合成数であることから間隔がいくらでも大きくなり、平方数の集合も間隔 $2n+1$ がいくらでも大きくなる。したがってどちらも最終的に周期的でなく、ex-pumping-regular-nonregular の 2・4 はこの命題からも分かる。逆に、たとえば偶数の長さの集合は $N=0$、$d=2$ で周期的なので、$\{1^{2n}\mid n\ge0\}$ は正規である。
逆が成り立たない例
$\Sigma=\{a,b,c\}$ 上の言語
$$
F:=\{a^ib^jc^k\mid i,j,k\ge0,\ i=1\text{ ならば }j=k\}
$$
は、thm-pumping-regular の結論を $p=2$ で満たすが、正規言語でない。
反復補題の結論：$w=a^ib^jc^k\in F$、$|w|\ge2$ とする。$i=0$ なら $x=\varepsilon$、$y$ を $w$ の先頭の 1 文字とすると、$xy^mz$ はどれも $a$ を含まない $b^{j'}c^{k'}$ の形で $F$ に属する。$i=1$ なら $x=\varepsilon$、$y=a$ とすると $xy^mz=a^mb^jc^j$ で、$m=1$ なら $w$ 自身、$m\ne1$ なら条件がかからないので $F$ に属する。$i=2$ なら $x=\varepsilon$、$y=aa$ とすると $a$ の個数 $2m$ は $1$ にならない。$i\ge3$ なら $x=\varepsilon$、$y=a$ とすると $a$ の個数 $i-1+m\ge2$ は $1$ にならない。どの場合も $|y|\ge1$、$|xy|\le2$ である。
正規でないこと：$F$ が正規なら、正規表現 $ab^{*}c^{*}$ の表す正規言語との共通部分 $F\cap ab^{*}c^{*}=\{ab^jc^j\mid j\ge0\}$ も正規である（正規言語 の記事の命題「補集合・共通部分・差に関する閉包性」）。この言語の反復定数を $q$ とし、$w=ab^qc^q$ に thm-pumping-regular を使う。$|xy|\le q$ なので $xy$ は $ab^{q-1}$ の中にある。$y$ が $a$ を含めば $xz$ は $a$ を含まず、含まなければ $y=b^r$（$r\ge1$）で $xz=ab^{q-r}c^q$ である。どちらでも $xz\notin\{ab^jc^j\}$ なので矛盾する。$\square$
この例では、文字列の先頭の $a$ を増減するだけで条件「$i=1$」から外れられるので、本当に正規性を壊している部分（$b$ と $c$ の個数の一致）に反復が届かない。共通部分をとって先頭を $a$ 1 個に固定すると、反復補題が効くようになる。正規であるための必要十分条件は、Nerode 同値関係の同値類が有限個であるという Myhill–Nerodeの定理 が与える。$F$ では $ab^n$（$n\ge0$）が互いに同値でないので、そこからも正規でないことが分かる。
仮定を外した場合
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 「$L$ が正規」 | $L_1=\{0^n1^n\}$ | どの $p$ でも、$w=0^p1^p$ に条件 1–3 を満たす分解がない |
| 条件 3 の「$m\ge0$」を「$m\ge1$」に弱めた形で正規性を測る | $L_3=\{0^i1^j\mid i>j\}$ | 弱めた形は $p=1$ で成り立つのに、$L_3$ は正規でない |
| 結論から正規性を逆に推す | prop-pumping-regular-converse-fails の $F$ | 結論を満たすのに正規でない |
2 行目：$L_3$ の元は $0$ で始まるので、$x=\varepsilon$、$y=0$ とすれば $xy^mz=0^{i+m-1}1^j$（$m\ge1$）では $i+m-1\ge i>j$ なので、$L_3$ に属する。ex-pumping-regular-nonregular の 3 は取り除く向き（$m=0$）で矛盾を導いており、条件 3 の $m=0$ は省けない。条件 2 は相手の選べる分解を先頭付近に限り、場合分けを減らすために使う。
補足
prop-pumping-regular-converse-fails の証明のように、閉包性と組み合わせると反復補題の適用範囲が広がる。たとえば $0$ と $1$ の個数が等しい文字列全体 $E$ は、正規なら正規言語 $0^{*}1^{*}$ との共通部分 $L_1=\{0^n1^n\}$ も正規になるので、ex-pumping-regular-nonregular の 1 から正規でない。正規言語の補集合も正規なので、言語が正規でないことを示すには、その補集合が正規でないことを示してもよい。
文脈自由言語にも、2 か所を同時に繰り返す形の反復補題がある（文脈自由言語 の記事の命題「文脈自由言語の反復補題」）。正規言語の反復補題は、DFA の状態という有限の記憶が長い文字列を区別しきれないことを述べ、文脈自由言語の場合は構文木の高さについての同じ型の議論になる。反復補題は MSm24 Theorem 2.9.1（pp. 69–70）にあり、証明もこの記事と同じく DFA の状態の重複による。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
