Советы по проверке языка не являются регулярными с использованием леммы Pumping

Question

Я пытаюсь доказать, что следующий язык не является регулярным, используя лемму прокачки

L = {aⁱ b^j | i = 2j для некоторого j ≥ 0}

Я решил выбрать s = a^2p b^p, таким образом |s| ≥ p, и я могу разбить его на три части xyz, где для каждого i ≥ 0, xyⁱ z ∈ L.

Любые советы для продолжения доказательства?

Спасибо!

Answer 1

Выберите s = a^2p b^p правильно!

Как сказал Грижеш Чаухан, мы должны ломать струны в L всеми возможными способами.

Таким образом, вы можете разделить с:

• х = а^к
• у =^л
• 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 содержит хотя бы одно 'a' (потому что |y|>0). Вы можете сказать, что L не является регулярным