Aritalab:Lecture/Automata/PumpingLemma

Revision as of 00:25, 2 June 2011

なぜ補題なのか

正規言語・文脈自由言語において、言語が受理する列の中にある特定部分列を任意の回数繰り返した列も必ず L で受理されることを示した定理を、ポンピング補題 (pumping lemma) と呼びます。具体的には以下の2種があります。

1. 正規言語におけるポンピング補題
2. 文脈自由言語におけるポンピング補題

いずれも与えられた言語が正規言語や文脈自由言語に含まれないことを示す証明に用いられるので、補題 (lemma) と呼ばれています。 またポンピング補題は言語を規定する必要条件であり、十分条件ではありません。これを満たすからといって正規言語や文脈自由言語であるとは限りません。

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

有限でない正規言語 L に属する任意の列 z についてある定数 K が存在し、以下が成立します。

1. z = xyz
2. |y| > 0, | xy | ≤ K
3. 任意の i に対して x yⁱ z ∈ L

正規言語 L に対応する有限オートマトン D を考えます。L は無限集合なので必ず D の状態数より長い列を受理し、その場合、同じ状態を2回以上通ります。この状態を訪れてから再び戻ってくるまでの最短列を y とすれば、上の補題が成立します。

文脈自由言語のポンピング補題

有限でない文脈自由言語 L についてある定数 K が存在し、L に属する任意の列 z ( |z| > K ) において以下が成立します。

1. z= uvwxy
2. vx ≠ ε
3. 任意の i に対し、uvⁱwxⁱy ∈ L

こちらも十分に長い文脈自由言語の導出を考え、同一の変数 X がその過程で 2 回以上現れる部分を考えます。こちらは絵を使って考えるとわかりやすく、文脈自由言語のページで説明しています。