ポンピング補題を使用して言語が規則的でないこと

Question

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

L = {^K B ^{3リットルリットル} |私はwを選択することを決定した≥ 0}

≥ 1、L = B k個^3PP、その後、| W | = 4p + 1 ≥ p

ヒント？

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

Answer 1

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

• 通常の言語は逆転で閉じられます。あなたは$ L^R = {a^l b^{3l} a^k} $を見ることができます。今では、最初のブロックにあるすべてのポンピングが言語の邪魔になります。
• 通常の言語は交差点で閉じられています。あなたがb + a +との交点を取ると$ {a b^{3l} a^k} $になり、今度はbブロックをポンピングするとあなたは言語の外に出るでしょう。