Лемма о накачке (Pumping lemma)

#теория_автоматов

Так как вопрос более относится к программированию нежели к математике я бы очень
хотел задать его здесь. Но местное форматирование не поддерживает использование формул
как на форуме математики. Поэтому прошу прощения, что я позволил себе оттуда утянуть
вопрос скриншотом сюда (Лемма о разрастании):


    

Ответы

Ответ 1

Для начала, язык A регулярен (например, он описывается регулярным выражением (ww)*).
Лемма о накачке не может быть использована для доказательства регулярности языка,
ведь она сформулирована для регулярных языков, и значит, выводит свойства из факта
регулярности. Если язык обладает свойством накачки (описанным в лемме), он может быть
и регулярным, и нерегулярным: лемма не запрещает нерегулярным языкам обладать этим
свойством.
При помощи леммы можно, однако, доказать нерегулярность языка: если условие накачки
не выполняется, язык точно не регулярный, от противного.
Приведённые вами соображения не доказывают нерегулярность, так как они не доказывают
невыполнение условия накачки. Условие накачки утверждает лишь, что для достаточно длинных
слов возможно накачиваемое разбиение, оно вовсе не требует, чтобы любое разбиение было
накачиваемым. То, что вы привели ненакачиваемое разбиение, не означает, что ненакачиваемого
разбиения не существует.
Если вы захотите доказать нерегулярность, вам придётся показать, что для любой наперёд
заданной длины найдётся слово, никакое разбиение которого не накачиваемо. (Но в нашем
случае это не удастся, потому что язык всё же регулярный.)
И да, вопрос скорее по математике, чем по программированию.


Ответ 2

Первое разбиение не подходит, потому что при четных i xy^iz не пренадлежит A. Второе
разбиение подходит под условия леммы, значит A регулярно.