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

Question

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

L= { a^i b^j | я ^2 > J}

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

Благодарю.

Answer 1

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

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

Правильный способ показать, что определенный язык 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.

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

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

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

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

Answer 2

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

а ^ 2b ^ 5

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

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

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

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

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

Х (-) Y (а)Z(abbbbb)

Если вы "накачаете" Y^i, выбрав 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 не> =