pumping-lemma - ポンピング補題で言語が不規則であることを証明する

Question

ポンピング補題を使用して、次の言語が規則的でないことを証明しようとしています

L={ a^ib^j | i^2 > j}

これに関するヒントはありますか？私は完全に立ち往生しています。

ありがとう。

Answer 1

ポンピング補題は次のように述べています: 言語 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 のメンバーにならない理由を示すことを忘れないでください。

ご不明な点がございましたら、お気軽にお問い合わせください:)

乾杯。

Answer 2

次の文字列を選択するとします。

a^2b^5

ああああ。これは言語にあります。

これで、対戦相手は XYZ を選択できます。

それらのオプション: 1.) X(空)Y(いくつかの a) 2.) X(いくつかの a)Y(いくつかの a といくつかの b) 3.) X(いくつかの a)Y(いくつかの a)

可能な選択肢に基づいて、Y^i を使用して Y をポンプアップします。ここで、i は選択した任意の数です。

1 を選ぶとします。)

X(-)Y(a)Z(abbbbb)

i = 0 を選択して Y^i を「ポンプ」すると、新しい文字列は abbbbb になります。これは言語にありません。

対戦相手の可能な選択肢ごとにこれを繰り返します。言語 L にない文字列を生成する方法で Y をポンプアップできれば、言語が規則的ではないことを証明することに成功しました。

Answer 3

上記の答えに対して、「ポンピング補題は次のように述べています。言語 A が正則である場合 => 数 p (ポンピング長) が存在する場合、s が |s| >= p となるような L 内の任意の文字列である場合、s は次のようになります。 s=xyz の 3 つのピースに分割され、次の条件を満たす:"

あなたは「言語Lが規則的であれば」という意味です

また、3 つの条件
1. xy^iz は、i>=0 ごとに L にある
2. |y|>=0
3. p>=|xy|

2 番目は |y| だけにする必要があります。> 0 ではない >=