Верно ли доказательство леммы о накачке из книги «Введение в теорию вычислений»?

Доказательство «выкачивания леммы» из книги ‹Введение в теорию вычислений› :

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

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

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

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


regular-language pumping-lemma finite-state-automaton
person Anonemous    schedule 28.05.2019    source источник
comment
Если нет строк длины не меньше p, то могут быть строки длины не больше p. Учитывая, что алфавит конечен и существует максимальная длина строки, язык конечен. Все конечные языки регулярны. Лемма о накачке верна. Книга правильная, но, возможно, можно было бы написать яснее.   -  person Welbog    schedule 28.05.2019

Ответы (1)


arrow_upward
1
arrow_downward

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

  1. Лемма о накачке утверждает: «Если язык регулярен, то все строки длины не менее p в этом языке обладают некоторыми свойствами». Если в вашем языке нет строк длины не менее p, то утверждение пусто верно в том смысле, что контрпримеров нет. «Если x, то y» математически истинно, если x ложно. «Если луна сделана из сыра, то я король Франции» — это математически верное утверждение. Это, возможно, немного отличается от того, как мы обычно используем условные предложения, когда мы предполагаем, что гипотеза обычно (условно, гипотетически) верна. Но в этом его формальный смысл.
  2. В любом языке, строки которого имеют длину не менее p, есть строки, длина которых строго меньше p. Поскольку длина строки должна быть неотрицательным целым числом, это означает, что существует конечное число длин. Поскольку длина каждой строки соответствует конечному числу возможных строк в алфавите языка, а сумма конечного числа конечных терминов должна быть конечной, любой такой язык должен быть конечным. Мы знаем, что конечные языки должны быть регулярными, независимо от того, что говорит лемма о накачке; в любом случае, лемма о накачке для обычных языков не касается этого случая, поэтому то, что здесь говорится, истинно или ложно, на самом деле не имеет значения. Было бы менее запутанно просто ничего не говорить для языков с более короткими строками, чем пытаться отметить, что его утверждения согласуются и для этих случаев.
person Patrick87    schedule 28.05.2019
comment
Если луна сделана из сыра, то я король Франции, я думаю, что это НЕИЗВЕСТНО, а не правда. потому что я тоже могу сказать Если луна сделана из сыра, то я НЕ король Франции - person Anonemous; 29.05.2019