S 研究室

ポンピング補題の証明問題

形式言語・オートマトン大学・大学院

反復補題 (pumping lemma) はある言語が正規言語や文脈自由文法でないことを示すときに使う定理である．正規言語に対する反復補題と文脈自由文法に対する反復補題 *1 は若干異なるから注意すべし．

正規言語のポンピング補題

言語 $L$ が正規言語ならば，以下の条件を満たす自然数 $p$ (ポンピング長) が存在する．

任意の $\sigma \in L$ に対して $|\sigma| \geq p$ ならば，以下の条件を満たすように $\sigma = \alpha \beta \gamma$ と分割できる．

$|\alpha \beta| \leq p$
$|\beta| > 0$
任意の $n \in \mathbb{N}$ *2 に対して $\alpha \beta^n \gamma \in L$

文脈自由文法のポンピング補題

言語 $L$ が文脈自由文法ならば，以下の条件を満たす自然数 $p$ (ポンピング長) が存在する．

任意の $\sigma \in L$ に対して $|\sigma| \geq p$ ならば，以下の条件を満たすように $\sigma = uvwxy$ と分割できる．

$|vwx| \leq p$
$|vx| > 0$
任意の $n \in \mathbb{N}$ に対して $uv^nwx^ny \in L$

証明問題の例

これはある大学院の入試で問われた問題です．

問題: 言語 $L = \{ (\verb|aa|)^n (\verb|bb|)^n | n \in \mathbb{N} \}$ が正規言語でないことを，ポンピング補題を用いて示せ．

解答: $L$ が正規言語であると仮定すると，ポンピング補題によりポンピング長 $p$ が存在する．

$\sigma = (\verb|aa|)^p (\verb|bb|)^p$ とすると， $\sigma \in L$ かつ $|\sigma| = 2p \geq p$ だからポンピング補題の 3 つの条件を満たすように $\sigma = \alpha \beta \gamma$ と分割できる．

$|\alpha \beta| \leq p$ ， $|\beta| > 0$ より， $\sigma$ は $\alpha = (\verb|aa|)^{p-l}, \beta = (\verb|aa|)^l, \gamma = (\verb|bb|)^p \ (l > 0)$ のように分割される．

任意の $n \in \mathbb{N}$ に対して $\alpha \beta^n \gamma \in L$ となるはずだが， $n = 0$ に対して $\alpha \beta^0 \gamma = (\verb|aa|)^{p-l} (\verb|bb|)^{p} \not\in L \ (l > 0)$ となり，矛盾が生じる．

よって， $L$ は正規でない．

*1: $uvwxy$ 定理と呼ばれたりする．

*2: $\mathbb{N}$ はゼロを含む自然数の集合とする．