86

私はこの質問を見て、ポンピング補題が何であるかについて興味がありました（ウィキペディアはあまり役に立ちませんでした）。

基本的に、言語が特定のクラスに属するためには真実でなければならない理論的証明であることは理解していますが、それ以上はよくわかりません。

非数学者/計算科学博士が理解できる方法で、かなり細かいレベルでそれを説明しようとする人はいますか?

4

9 に答える 9

161

ポンピング補題は、言語が規則的ではないことを示す単純な証明です。つまり、有限状態マシンを構築できないことを意味します。標準的な例は language(a^n)(b^n)です。aこれは、任意の数のの後に同じ数の が続く単純な言語ですb。だから弦は

ab
aabb
aaabbb
aaaabbbb

などは言語ですが、

aab
bab
aaabbbbbb

などではありません。

これらの例の FSM を構築するのは簡単です。

FSM

これは n=4 までずっと機能します。問題は、私たちの言語が n に制約を課していないことです。有限ステート マシンは有限でなければなりません。このマシンにいくつの状態を追加しても、n が状態の数に 1 を加えた値に等しい入力を誰かが与えることができ、私のマシンは失敗します。したがって、この言語を読み取るように構築されたマシンが存在する可能性がある場合、状態の数を有限に保つために、そこのどこかにループが必要です。これらのループを追加すると:

FSM 2

私たちの言語の文字列はすべて受け入れられますが、問題があります。最初の 4 秒後、マシンは同じ状態のままであるため、a何回入力されたかのカウントを失います。aつまり、4 つaを超えると、文字列に s を追加せずに必要なだけbs を追加しても、同じ戻り値を取得できます。これは、文字列が次のことを意味します。

aaaa(a*)bbbb

(a*)任意の数のsを表すaと、明らかにすべてが言語であるわけではありませんが、マシンによってすべて受け入れられます。このコンテキストでは、ストリングの一部を(a*)ポンピングできると言えます。有限状態マシンが有限であり、n が制限されていないという事実は、言語内のすべての文字列を受け入れるすべてのマシンがこのプロパティを持たなければならないことを保証します。マシンはある時点でループする必要があり、ループした時点で言語をポンピングできます。したがって、この言語用に有限ステート マシンを構築することはできず、言語は規則的ではありません。

正規表現と有限ステート マシンは同等であることを思い出してください。次に、aとを Html の開始タグと終了タグに置き換えてb、相互に埋め込むことができます。正規表現を使用して Html を解析できない理由がわかります。

于 2009-12-19T16:46:47.537 に答える
9

素人の言葉で理解するのは難しいことですが、基本的に、正規表現には空でない部分文字列が含まれている必要があります。これは、新しい単語全体がその言語で有効なままである間、何度でも繰り返すことができます。

実際には、ポンピング補題は言語が正しいことを証明するのに十分ではありませんが、ポンピング補題が適合することを示すことによって、矛盾による証明を行い、言語が言語のクラス (通常または文脈自由) に適合しないことを示す方法としては不十分です。それには機能しません。

于 2009-01-20T15:03:51.727 に答える
4

単純な反復補題は、特に有限オートマトンによって記述される文字列のセットである正規言語の補題です。有限自動化の主な特徴は、その状態によって記述される有限量のメモリしかないことです。

ここで、有限オートマトンによって認識され、自動化のメモリを「超える」のに十分な長さの文字列があるとします。つまり、状態を繰り返す必要があります。次に、サブストリングの先頭のオートマトンの状態がサブストリングの末尾の状態と同じであるサブストリングがあります。サブストリングを読み取っても状態は変わらないため、オートマトンが賢明でなくても、サブストリングは任意の回数削除または複製される可能性があります。したがって、これらの変更された文字列も受け入れる必要があります。

また、文脈自由言語には、文字列の2つの場所で括弧が一致していると直感的に見なされる可能性のあるものを削除/挿入できる、やや複雑なポンピング補題があります。

于 2009-01-20T15:47:55.867 に答える
4

基本的に、(XML のような) 言語の定義があります。これは、特定の文字列 (「単語」) がその言語のメンバーであるかどうかを判断する方法です。

ポンピング補題は、言語から「単語」を選択し、それにいくつかの変更を適用できる方法を確立します。定理は、言語が規則的である場合、これらの変更は同じ言語からの「単語」を生成するはずであると述べています。思いついた単語がその言語にない場合、その言語はそもそも規則的ではなかったはずです。

于 2009-01-20T15:00:36.227 に答える
0

定義上、通常の言語は、有限状態オートマトンによって認識される言語です。迷路と考えてください。状態は部屋であり、トランジションは部屋間の一方通行の廊下であり、最初の部屋と出口 (最終) の部屋があります。「有限状態オートマトン」という名前の通り、部屋の数は有限です。廊下を進むたびに、壁に書かれた文字を書き留めます。最初の部屋から最後の部屋まで、その文字でラベル付けされた廊下を正しい順序で通過するパスを見つけることができれば、単語を認識できます。

ポンピング補題によると、一度通った部屋に戻らずに迷宮をさまようことができる最大の長さ (ポンピング長) があるということです。アイデアは、あなたが歩くことができる個別の部屋が非常に多いため、特定のポイントを過ぎて、迷宮を出るか、トラックを横断する必要があるということです. 迷宮でこのポンピングの長さよりも長い道を歩くことができた場合は、迂回しています: 道に (少なくとも 1 つの) サイクルを挿入しているため、削除することができます (迷宮を横断したい場合)。より短い単語を認識する) または無限に繰り返される (ポンピングされる) (非常に長い単語を認識できるようにする)。

文脈自由言語にも同様の補題があります。これらの言語は、実行する遷移を決定するためにスタックを利用できる有限状態オートマトンであるプッシュダウン オートマトンによって受け入れられる単語として表すことができます。それにもかかわらず、有限数の状態がまだ存在するため、プロパティの形式的な表現が少し複雑になる可能性があっても、上記で説明した直感が引き継がれます。

于 2009-04-30T18:34:58.570 に答える
0

素人の言葉で言えば、ほぼ正しいと思います。これは、言語が特定のクラスにないことを証明するための証明手法 (実際には 2 つ) です。

たとえば、無限の数の文字列を持つ通常の言語 (正規表現、オートマトンなど) を考えてみましょう。ある時点で、starblue が言ったように、文字列がオートマトンに対して長すぎるため、メモリが不足します。これは、オートマトンが文字列のコピーの数を判断できない文字列のチャンクが必要であることを意味します (ループに入っています)。したがって、文字列の途中にその部分文字列の任意の数のコピーがあっても、あなたはまだその言語にいます。

これは、このプロパティを持たない言語を使用している場合、つまり、部分文字列を含まない十分に長い文字列があり、何度でも繰り返してもその言語にとどまることができる場合、その言語は規則的ではないことを意味します。

于 2009-04-30T18:49:21.857 に答える
0

たとえば、この言語L = a n b nを取り上げます。

次に、上記の言語の有限オートマトンをいくつかのnについて視覚化してみてください。

n = 1 の場合、文字列w = ab。ここで、n = 2 の場合、文字列w = a 2 b 2のループを使用せずに有限オートマトンを作成できます。ここで、アウトループなしで有限オートマトンを作成できます

n = pの場合、文字列w = a p b p。基本的に、有限オートマトンは 3 ステージであると見なすことができます。第 1 段階では、一連の入力を受け取り、第 2 段階に入ります。同様にステージ 2 からステージ 3 まで。これらのステージをx、yおよびzと呼びましょう。

いくつかの観察があります

  1. 間違いなくxには 'a' が含まれ、zには 'b' が含まれます。
  2. ここで、 yについて明確にする必要があります。
    • ケースa : yには 'a' のみを含めることができます
    • ケースb : yには 'b' のみを含めることができます
    • ケースc : yには 'a' と 'b' の組み合わせが含まれる場合があります

したがって、ステージyの有限オートマトン状態は、入力 'a' と 'b' を受け取ることができる必要があり、また、数えられない a と b をそれ以上取ることはできません。

  1. ステージyが 1 つの 'a' と 1 つの 'b' のみを取る場合、2 つの状態が必要です。
  2. 2 つの 'a' と 1 つの 'b' を使用する場合、out ループなどを使用せずに 3 つの状態が必要です....

したがって、ステージyの設計は純粋に無限です。いくつかのループを配置することによってのみ有限にすることができ、ループを配置すると、有限オートマトンはL = a n b nを超える言語を受け入れることができます。したがって、この言語では、有限オートマトンを構築することはできません。したがって、それは規則的ではありません。

于 2010-10-26T07:08:00.247 に答える
-1

これはそれ自体の説明ではありませんが、簡単です。a^nb^n の場合、FSM は、b が既に解析された a の数を認識し、同じ n 個の b を受け入れるように構築する必要があります。FSM は単純にそのようなことを行うことはできません。

于 2012-03-07T13:04:34.693 に答える