regular-language - Pumping Lemma を使用して言語が規則的でないことを証明する

Question

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

L = {a ^k b ^3l a ^l | k ≥ 1 , l ≥ 0}

w = ab ^3p a ^pを選択し、次に |w|を選択することにしました。= 4p+1 ≥ p

任意のヒント？

ありがとうございました！

Answer 1

あなたが使用しているポンピング補題の正確な定式化についてはわかりません。いずれにせよ、ウィキペディアのような標準的な定式化では、固定長のプレフィックスのどこかにしかポンピングできないため、これはかなりトリッキーなケースです。ただし、 a の最初のブロックはどこでもポンピングでき、任意に長くすることができます。したがって、追加のプロパティを使用する必要があります。私は2つを提案します：

• 通常の言語は反転で閉じられます。したがって、$L^R = {a^lb^{3l} a^k}$ を見たほうがよいでしょう。これで、a の最初のブロックでポンピングを行うと、言語から抜け出すことができます。
• 常用言語は交差点の下で閉鎖されています。a b+ a+ との交点を取ると、最終的に ${ab^{3l} a^k}$ になり、b ブロックをポンピングすると言語から抜け出します。