ポンピング補題は 2 つあり、1. 通常言語、2. コンテキスト - 自由言語に対して定義されています。 通常言語のポンピング補題 任意の正規言語 L に対して、すべての x に対して次のような整数 n が存在します。 L と |x| ? n、u、v、wは存在しますか？ ?^*、 x = uvw 、および (1) |uv| となります。 ? n (2) |v| ?すべての i に対して 1 (3) ? 0: 紫外線^私ｗ？ L 簡単に言えば、これは、文字列 v が「ポンピング」された場合、つまり、v が何度挿入された場合でも、結果の文字列は依然として L に残ることを意味します。ポンピング補題は、言語の不規則性の証明として使用されます。したがって、言語が正規であれば、ポンピング補題を常に満たします。 L に存在しないポンピングから作られた文字列が少なくとも 1 つ存在する場合、L は確実に正規ではありません。この逆が常に真実であるとは限りません。つまり、ポンピング補題が成り立つとしても、言語が規則的であることを意味するわけではありません。

それ以外の場合はJavaで

たとえば、L を証明しましょう₀₁= n ? 0は不規則です。 L が正則であると仮定すると、ポンピング補題によって上記の規則が適用されます。さて、x としましょう? L と |x| ? n.したがって、ポンピング補題により、(1) – (3) が成り立つような u、v、w が存在します。すべての u、v、w について、(1) ～ (3) が成り立たないことを示します。 (1) と (2) が成立する場合、x = 0ⁿ1ⁿ= |uv| を使用した uvw ? n と |v| ? 1. したがって、u = 0^ある、v = 0^b、w = 0^c1ⁿここで、 a + b ?ん、ｂ？ 1、c? 0、a + b + c = n しかし、i = 0 uv の場合 (3) は失敗します。⁰w = uw = 0^ある0^c1ⁿ= 0^{a + c}1ⁿ? L、a + c なので? n.

文脈自由言語 (CFL) のポンピング補題 CFL のポンピング補題では、任意のコンテキスト自由言語 L について、何度でも「ポンピング」でき、依然として同じ言語にある 2 つの部分文字列を見つけることが可能であると述べています。任意の言語 L について、その文字列を 5 つの部分に分割し、2 番目と 4 番目の部分文字列をポンプします。ここでも、ポンピング補題は、言語が CFL ではないことを証明するツールとして使用されます。条件を満たさない文字列が 1 つでもある場合、その言語は CFL ではないからです。したがって、L が CFL の場合、すべての x について次のような整数 n が存在します。 L と |x| ? n、u、v、w、x、yは存在しますか? ?^*、x = uvwxy、および (1) |vwx| となります。 ? n (2) |vx| ?すべての i に対して 1 (3) ? 0: 紫外線^私wx^私そして ？私

上の例では、0ⁿ1ⁿは CFL です。どの文字列も 2 つの場所 (1 つは 0、もう 1 つは 1) でポンピングされた結果である可能性があるためです。証明しましょう、L₀₁₂= n ? 0 はコンテキストフリーではありません。 L が文脈自由であると仮定すると、ポンピング補題により、上記の規則が続きます。さて、x としましょう? L と |x| ? n.したがって、ポンピング補題により、(1) – (3) が成り立つような u、v、w、x、y が存在します。すべての u、v、w、x、y について (1) – (3) が成り立たないことを示します。 (1) と (2) が成立する場合、x = 0ⁿ1ⁿ2ⁿ= uvwxy と |vwx| ? n と |vx| ? 1. (1) は、vwx に 0 と 2 の両方が含まれていないことを示しています。したがって、vwx には 0 がないか、vwx には 2 が含まれていません。したがって、考慮すべき 2 つのケースがあります。 vwx に 0 がないものとします。 (2) により、vx には 1 または 2 が含まれます。したがって、uwy には「n」個の 0 があり、uwy には「n」個未満の 1 が含まれるか、「n」個未満の 2 が含まれます。しかし、(3) は uwy = uv であることを示しています。⁰wx⁰はい？ L. つまり、uwy には同じ数の 0、1、2 が含まれており、矛盾が生じます。 vwx に 2 がない場合も同様ですが、矛盾が生じます。したがって、L は文脈自由ではありません。出典: John E. Hopcroft、Rajeev Motwani、Jeffrey D. Ullman (2003)。オートマトンの理論、言語、計算の紹介。

Javaジェネリックス

この記事は次の寄稿者により提供されました ニルパム・シン 。