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

Question

Доказательство "леммы накачки" из книги " Введение в теорию вычислений":

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

1. для каждого i ≥ 0 xyiz ∈ A,
2. | У | > 0 и
3. | Х | ≤ р

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

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

Answer 1

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

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