theory - 正規言語のポンピング補題の詳細

Question

正規言語のポンピング補題について 1 つ小さな質問があります。言語 L に属する特定の文字列をポンピングできない場合、その言語は不規則であることを示すのに十分でしょうか? たとえば、a^nb^n (ab、aabb、aaabbb ...) という形式の言語 L1 を選択し、文字列 aabb をポンピングできず、依然として L1 の一部であることを示した場合、それはL1が不規則であるとすぐに結論付けるのは正しいですか?

乾杯。

Answer 1

はい、それがポンピング補題の仕組みです。言語が規則的でないことを証明する場合にのみ役立ちます。ポンピング補題を満たすことは、言語が規則的であるための必要条件であり、十分条件ではありません。

(注意: 文脈自由言語とそこにあるそれぞれのポンピング補題についても同様)

Answer 2

はい、これはどのように機能するかですが、文字列が「ポンピングできない」方法を示す際には注意してください

これを行うには、Lの文字列wを部分文字列xyzに分割し、一部のバージョンのxy ^ 1z（int i i> = 0の場合）がLにない文字列につながることを示す必要がありますが、DFA Mによって受け入れられます（Mビルドの場合） L）を受け入れるために、矛盾に到達します。

yの位置を選択することはできないため、3つの可能な位置を考慮する必要があることに注意してください。私の意見では、それが鍵です。

Answer 3

1 つの有限長の文字列がポンピングしないことを示すだけでは十分ではありません。厳密な議論の場合、サンプル文字列の長さが言語のポンピング長よりも大きいことも証明する必要があります。通常、ポンピング長 p が存在すると仮定し、ポンピングできない p よりも長い文字列を作成します。

Answer 4

ポンピング補題は次のように述べています: 言語 A が正則である場合 => 数値 p (ポンピング長) が存在する場合、s が |s| となるような L 内の任意の文字列である場合 >= p の場合、s は次の条件を満たす 3 つの部分 s=xyz に分割できます。

1. xy ⁱ z は、i>=0 ごとに L にあります
2. |y|>=0
3. p>=|xy|

ある言語 L が正則でないことを示す正しい方法は、L が正則であると仮定し、矛盾に到達しようとすることです。

L = {0 ⁿ 1 ⁿ }|n>=0} が正則でないことを実証してみましょう。逆に、L が正則であると仮定し始めます。

この種のデモンストレーションをゲームとして考えることができます:
チャレンジャー:彼はポンピングの長さ p を選択します。それについて推測することはできません。
あなた: 次はあなたの番です。言語の不規則性を表す文字列の「種類」を選択してください。
文字列が 0 ^p 1 ^pの形式であるとしましょう。
このステップでの良いヒントは、敵の次の動きを制限しようとすることです。
挑戦者:彼はあなたに 0 ^p 1 ^pの形の文字列 s を提示します。
You:パンプする時間です！前の手で弦の形を正しく選択した場合は、いくつかの仮定を行うことができます。
たとえば、私たちの場合、|xy|<=p で最初の p 要素が 0 であるため、部分文字列 y が 0 のみで構成されていることがわかります (|y|>0 のため、少なくとも 1 つの 0)。

ここで、xy ⁱ z が L にないような i>=0 が存在することを示します。たとえば、i=2 の場合、文字列 xyyz は 1 よりも 0 の方が多いため、L のメンバーではありません。このケースは矛盾しています。=> L は正則ではありません。

ポンピングされた文字列が L のメンバーにならない理由を示すことを忘れないでください。

多分あなたを助けるのが遅いですが、他の誰かがこの種の説明を必要とするかもしれません...多分^^

乾杯。