Насосная Лемма Помощь

Question

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

Язык для доказательства является нерегулярным: L = {aⁱ b^j c^k: i = j или j = k}

Определение леммы прокачки, которое я дал, состоит в следующем:

1. противник выбирает м
2. Я хочу выбрать w, чтобы противоречить лемме прокачки. Используйте m, чтобы выбрать строку w ∈ L, где |w| ≥ м
3. оппонент выбирает разложение w с учетом ограничений.
4. Я пытаюсь выбрать i так, чтобы перекачанная колонна w_i ∉ L. Если найдено, L не является регулярным

Этот предмет оказался для меня очень трудным для понимания, и из-за этого я чувствую себя полным вздохом, поэтому было бы полезно получить подробное объяснение того, как правильно применять лемму накачки.

Answer 1

Интуитивно, лемма прокачки говорит, что достаточно длинные слова (длина зависит только от языка L) в обычном языке L должны содержать раздел (длиной> 0), который можно повторять так часто, как это необходимо. Повторение этого раздела ("прокачка" исходного слова) любое количество раз приводит к появлению более длинных слов, также присутствующих в языке L.

Минимальная длина слова - это m на первом шаге приведенного выше определения; количество повторений раздела - это 4-й шаг приведенного выше определения.

Лемма прокачки обычно используется, чтобы показать, что язык L не является регулярным. Это доказательство от противного: предположим, что L является регулярным, и, следовательно, лемма прокачки для регулярных языков верна для L. Затем выберите слово w, которое находится в L достаточной длины *, и покажите, что независимо от того, как оно разлагается *, некоторая накачка слово не в языке. Это противоречит лемме прокачки - что мы знаем, чтобы быть правдой. Таким образом, наше предположение о том, что язык является регулярным, было неверным, и, следовательно, язык не является регулярным. Части, отмеченные *, не могут быть выбраны, чтобы упростить задачу - поэтому на шагах 1 и 3 "противник" выбирает их.

Слово w переписывается как w = x y z, где | у | > 0 и |x y| <= м. И x, и z могут иметь длину 0.

Обычный подход состоит в том, чтобы выбрать xy как строку, состоящую из одной и той же буквы, так что наличие большего количества этой же буквы (после прокачки) приводит к слову не в L.

Никаких ограничений не указано для i или k на языке L в посте, поэтому при условии, что i = 0 разрешено, подходящим словом может быть b^m c^m (то есть m bs, за которым следует m cs). Теперь, какую бы декомпозицию ни выбрал оппонент, y всегда будет состоять из нескольких bs. Повторение этих bs приводит к слову с большим количеством bs, чем cs, и без as as, и, следовательно, i!= J и j!= K, и это слово отсутствует в языке.