Является ли доказательство леммы накачки неправильным из книги <Введение в теорию вычислений>?

Question

Доказательство «леммы накачки» из книги <<a href="https://books.google.com/books/about/Introduction_to_the_Theory_of_Computatio.html?id=P3f6CAAAQBAJ&printsec=frontcover&source=kp_read_button#v=onepage&q&f=false" rel="nofollow noreferrer"> Введение в теорию вычислений >:

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

1. для каждогоi ≥ 0, xyiz ∈ A,
2. | y |> 0 и
3. | xy |≤ p

Пусть M = (Q, Σ, δ, q1, F) - DFA, который распознает A. Мы назначим длину накачки p как число состояний M. Покажем, чтолюбая строка s в A длиной не менее p может быть разбита на три части xyz, удовлетворяющие нашим трем условиям. Что если строки в A не имеют длину не менее p?Тогда наша задача становится еще проще, потому что теорема становится бессмысленной: очевидно, что три условия выполняются для всех строк длины, по крайней мере, p, если таких строк нет .

Вопрос:смелая цитата часть, которую я считаю неправильной.Потому что, если ни одна строка в A не имеет длины, по крайней мере, p, то это явно не обычный язык.

Answer 1

Здесь необходимо уточнить два момента:

1. Насосная лемма гласит: «Если язык регулярный, то все строки длиной не менее p в этом языке имеют некоторые свойства». Если в вашем языке нет строк длиной, по крайней мере, p, то оператор vacuously true в том смысле, что нет контрпримеров. «Если x, то y» математически true , если x равно false. «Если луна сделана из сыра, то я король Франции» - математически истинно утверждение. Возможно, это немного отличается от того, как мы обычно используем условные выражения, когда мы предполагаем, что гипотеза обычно (условно, гипотетически) верна. Но это его формальное значение.
2. Любой язык, строки которого имеют длину не менее p, имеет строки, длина которых строго меньше p. Поскольку длина строки должна быть неотрицательным целым числом, это означает, что существует конечное число длин. Поскольку каждая длина строки соответствует конечному числу возможных строк в алфавите языка, а сумма конечного числа конечных членов должна быть конечной, любой такой язык должен быть конечным. Мы знаем, что конечные языки должны быть регулярными, независимо от того, что говорит насосная лемма; в любом случае, лемма прокачки для обычных языков не имеет отношения к этому случаю, так что то, что говорит «правда» или «ложь», здесь действительно не имеет значения. Было бы менее странно просто ничего не говорить для языков с более короткими строками, чем пытаться заметить, что его утверждения согласуются и с этими случаями.