Докажи язык нерегулярным с прокачкой леммы

Question

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

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

Есть какие-нибудь советы по этому поводу?Я полностью застрял.

Спасибо.

Answer 1

Лемма прокачки гласит: Если язык A регулярный =>, существует число p (длина накачки), где, если s - любая строка в L такая, что | s | > = p, то s можно разделить на три части: s = xyz, удовлетворяющих следующему условию:

1. xy ⁱ z находится в L для каждого i> = 0
2. | y |> = 0
3. p> = | xy |

Правильный способ показать, что определенный язык L не является регулярным, состоит в том, чтобы предположить, что L является регулярным, и попытаться достичь противоречия.

Давайте попробуем продемонстрировать, что L = {0 ⁿ 1 ⁿ } | n> = 0} не является регулярным. Мы начинаем предполагать, что L регулярна.

Вы можете думать об этой демонстрации как об игре:
Претендент: Он выбирает длину прокачки с. Вы не можете делать какие-либо предположения об этом.
Вы : Теперь ваша очередь: выберите «вид» строки, которая представляет неправильность языка.
Допустим, строка имеет вид 0 ^p 1 ^p .
Хороший совет на этом этапе - попытаться ограничить противника следующим ходом.
Претендент: Он представляет вам строку s в форме 0 ^p 1 ^p .
Вы: Пора прокачать! Если вы правильно выбрали форму строки в предыдущем шаге, вы можете сделать некоторые предположения.
В нашем случае, например, мы знаем, что подстрока y состоит только из 0s (по крайней мере, один 0, потому что | y |> 0), потому что | xy | <= p и первые p-элементы равны 0s. </p>

Теперь мы покажем, что он существует i> = 0 так, что xy ⁱ z отсутствует в L. Например, для i = 2 строка xyyz имеет больше 0s, чем 1s, и поэтому не является членом Л. Этот случай противоречие. => L не является регулярным.

Никогда не забывайте демонстрировать, почему накачанная колонна не может быть членом L.

Если у вас есть какие-либо сомнения, не стесняйтесь спрашивать :)

Приветствие.

Answer 2

Допустим, вы выбрали строку:

a ^ 2b ^ 5

aabbbbb.Который на языке.

Теперь ваш оппонент может выбрать XYZ.

Их варианты: 1.) X (пусто) Y (некоторые a's) 2.) X (некоторые a's) Y (некоторые a и некоторые b) 3.) X (некоторые a) Y (некоторые a)

Основываясь на их возможном выборе, вы накачиваете Y, используя Y ^ i, где i - произвольное число по вашему выбору.

Скажем, они выбирают 1.)

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

Если вы «накачаете» Y ^, я выберу i = 0.новая строка становится abbbbb.Что не на языке.

Повторите это для каждого возможного выбора оппонента, если вы можете накачать Y таким образом, что получается строка, не на языке L, то вы преуспели вдоказывая, что язык не является регулярным.

Answer 3

На приведенный выше ответ: «Лемма прокачки гласит: если язык A регулярный => существует число p (длина прокачки), где, если s - любая строка из L такая, что | s |> = p, тоs можно разделить на три части: s = xyz, удовлетворяя следующему условию: «

Вы имеете в виду« Если язык L регулярный »

Кроме того, три условия
1. xy^ iz находится в L для каждого i> = 0
2. | y |> = 0
3. p> = | xy |

Второе должно быть просто | y |> 0 не> =