Есть ли в обычном языке L бесконечные слова?

Это странно, но прокачивая лемму, скажем

Позволять L будь обычным языком. Существует постоянная n такой, что для каждой строки w в L такой, что |w| >= nмы можем сломать w в к xyz такой, что xy*z также в L,

Эта лемма сильна, потому что она доказывает для всех обычных языков. Но что, если обычный язык L = a? Есть только одно слово (a) в этом. Как работает лемма прокачки в этом случае?

1 ответ

Если n = 2 тогда это правда, что любой w в L с |w| >= n удовлетворяет выводу леммы накачки. Нет слов в L достаточно длинные, чтобы служить контрпримерами. В целом, если L любой конечный язык тогда L удовлетворяет лемме прокачки: просто возьми n быть больше, чем длина самого длинного слова в L,

Другие вопросы по тегам