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

Question

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

L = {a ⁱ b ^j | i = 2j for some j ≥ 0}

このようにs = a ^2p b ^pを選択することにしました |s| ≥ p で、それを 3 つの部分 xyz に分割できます。ここで、i ≥ 0 ごとに xy ⁱ z ∈ Lです。

証明を続けるためのヒントはありますか?

ありがとう！

Answer 1

s = a ^2p b ^pを選択してください。

Grijesh Chauhan が言ったように、可能な限りすべての方法で L の文字列を分割する必要があります。

したがって、 s を次のように分割できます。

• x= ^k
• y=^アル
• z=a ^2p-kl b ^p

ここで |xy|≥ 0 かつ |y|>0 です。

i=2 とすると、xy ² zが得られます。

• s = a ^k a ^l a ^l a ^2p-kl b ^p

あれは：

• s = a ^2p+l b ^p

l には少なくとも 1 つの 'a' が含まれているため (|y|>0 であるため)。L は正則ではないと言えます