Насосная лемма для обычного языка

Question

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

Предположим, мы должны проверить:

Язык принимающий четное число 0 в обычном или нет?

Мы знаем, что это регулярно, потому что мы можем построить DFA для L. Но я хочу доказать это с помощью леммы прокачки.

Теперь предположим, что я беру строку w= "0000":

Теперь разделим строку как x = 0, y = 0, а также z = 00, Теперь о применении насосной леммы для i = 2 Я получу строку "00000", чего нет в моем языке, поэтому, используя лемму, докажи, что язык не является регулярным. Но это принято DFA?

Любая помощь будет оценена
Спасибо

Answer 1

Вы не совсем ясно о прокачке леммы.

Что говорит прокачка леммы:

Формальное определение: прокачка леммы для регулярных языков

Позволять L будь обычным языком. Тогда существует целое число p≥ 1 в зависимости только от L так, что каждая строка w в L длиной не менее p (p называется "pumping length") можно записать как w знак равно xyz (То есть, w можно разделить на три подстроки), удовлетворяя следующим условиям:

1. |y| ≥ 1
2. |xy| ≤p
3. для всех i≥ 0, xyiz∈L

Но это утверждение говорит о том, что:

Если язык действительно является обычным языком, то должен быть какой-то способ генерировать (качать) новые строки из всех достаточно больших строк.

1. Достаточно большая строка означает строку на языке длиной ≥ P.
   _{Таким образом, может быть невозможно создать новую строку из небольших строк, даже если язык является Regular Language}

2. Что-то значит, если язык действительно регулярный и наш выбор w верно. Тогда должен быть хотя бы один способ сломать w в трех частях xyz такой, что повторяя (прокачка) y для любого количества раз мы можем генерировать новые строки в языке.
   _{правильный выбор} w _{средства:} w _{на языке и достаточно большой ≥ P}

примечание: во втором пункте может быть шанс, что даже если вы сломаете w правильно в xyz в соответствии с формальным определением все еще некоторые новые сгенерированные строки не на языке. Как и вы.

И в этой ситуации вы должны повторить с другим возможным выбором y,

В выбранной вами строке w = " 0000 " вы можете сломать w такой, что y = 00, И с этим выбором y вы всегда найдете новую сгенерированную строку в языке, которая является "четным числом нулей"

_{Одна ошибка, которую вы делаете в своем доказательстве того, что вы делаете для конкретной строки 0000. Вы должны подтвердить для всех} w _{≥ P. Так что ваше доказательство еще неполное}

Прочитайте мой ответ в КОНТЕКСТЕ ЛЕММЫ НАСОСА ДЛЯ РЕГУЛЯРНЫХ ЯЗЫКОВ

В этом ответе я объяснил, что нарушение w в xyz и прокачка y означает поиск зацикливания и повторение зацикливания, чтобы генерировать новые строки в языке.
Когда мы докажем, что какой-то язык является регулярным; тогда на самом деле мы не знаем, где находится циклическая часть, поэтому мы пробуем все возможные варианты, которые удовлетворяют правилу 1,2 и 3 леммы накачки.

А лемма прокачки говорит, что если язык регулярен и бесконечен, то в DFA должен быть цикл, и каждая достаточно большая строка в языке проходит через циклическую часть (в соответствии с принципом голубя) DFA (и, следовательно, y не может быть нулевым Это правило-1 в приведенном выше формальном определении).

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

Но на самом деле мы не знаем, где находится петля в DFA, поэтому мы стараемся всеми возможными способами.

Чтобы убедиться, что язык является регулярным: вы должны доказать, что для всех достаточно длинных строк (w) в языке существует как минимум один способ (y) генерировать новые строки в языке, повторяя часть цикла любое число (i) раз,

Доказательство языка не является регулярным: вы должны найти по крайней мере одну достаточно длинную строку (w) в языке, чтобы не было выбора для любого способа 'y', чтобы можно было генерировать новые строки со всеми возможными повторениями (i).

To proof using Pumping Lemma: 
+-------------------------+--------------------------+----------------+--------------+
|                         | Sufficient large W in L  |     y          |    i >=0     |
+-------------------------+--------------------------+----------------+--------------+
| language is regular     | For all W (all W can use | At-least one   | For all i>=0 |  
|                         | to generate new W' in L) |                |              |
+-------------------------+--------------------------+----------------+--------------+
| language is NOT regular | Find Any W (at-least 1   | With all (Show | At-least one |   
|                         | W that can't generates   | no possible Y  | i            | 
|                         | new W' in L              | exists)        |              |
+-------------------------+--------------------------+----------------+--------------+

ВНИМАНИЕ:: Правило всегда не работает, чтобы доказать, "Погода ли язык является регулярным?"

Накачка леммы необходимое, но не достаточное условие для того, чтобы язык был регулярным. Возможный язык, который удовлетворяет этим условиям, может все еще быть нерегулярным.
Ссылка

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

Answer 2

Хотя принятый ответ по-своему завершен, мне пришлось добавить несколько вещей. У меня есть очень забавный способ использовать лемму о накачке, чтобы доказать, что данный язык не является регулярным языком. Позвольте мне сформулировать лемму, чтобы поговорить о контексте.

Лемма о накачке для регулярных языков:

Для любого регулярного языка L существует целое число k.

Такой, что для всех x ∈ L с |x| ≥ k, существуют такие u, v, w ∈ Σ∗, что x = uvw и

(1) | УФ | ≤ k

(2) |v| ≥ 1

(3) для всех i ≥ 0: u(v^i)w ∈ L

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

Теперь, чтобы начать игру, вам понадобятся два игрока. Один - Читатель (R), а другой - Противник (A).

Ввод: язык L

Цель R: Каким-то образом докажите, что язык L не является регулярным, с помощью некоторого противоречия.

Цель A: Каким-то образом будьте готовы встретить аргументы R и не позволяйте ему создавать противоречие.

А теперь давайте начнем спор.

A: Язык L не является неправильным, потому что никто не может показать противоречие, используя лемму о накачке с определенной константой накачки k. (Каждый язык отображается только на одно целое число k)

R: Позвольте предположить, что вы говорите. Если язык L регулярен, то он должен удовлетворять условиям леммы о накачке. Итак, позвольте мне выбрать подходящую строку x ∈ L (|x| >= k), которая поможет мне впоследствии создать противоречие.

A: Оспаривается R, A пытается найти хотя бы одно подходящее разбиение u, v и w строки x, такое, что

x = uvw  and |uv| <= k and |v| > 0

R: С любым возможным разделом, заданным A, выигрывает аргумент, если может показать целое число i >= 0 такое, что

u(v^i)w ∉ L

Потому что теперь Rпоказал, что в языке L есть по крайней мере одна строка x, которая не имеет никакого разбиения (u, v, w), так что она удовлетворяет лемме о накачке. Противоречие произошло потому, что наше предположение о регулярности L неверно. FALSE. Таким образом, доказано, что язык L не является регулярным.

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

Всегда помните, что лемма о накачке if(L регулярно), thenЗаявления. Обратное не обязательно TRUE. Хотя может быть TRUE в некоторых случаях.

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

(Источник: Теория вычислений (NPTEL): профессор Соменат Бисвас (ИИТ Канпур)