3622
правки
Изменения
м
→Пример языка, удовлетворяющего лемме в общем виде
'''Докажем, что он нерегулярный.''' Предположим, что некоторая строка языка <tex>L</tex> имеет длину <tex>n=5</tex>. Поскольку в алфавите всего четыре символа, то как минимум два символа из пяти в этой строке будут одинаковыми, и они разделены максимум тремя символами:
:Если дубликаты разделены нулями или единицами, накачаем один из двух остальных символов в строке, которые не повлияют на подстроку, которая содержит дубликаты,.:Если дубликаты разделены двойками или тройками, накачаем <tex>2</tex> символа, разделяющих их. Накачка также уменьшает или увеличивает результат во время создания подстроки размера <tex>3</tex>, которая содержит <tex>2</tex> продублированных символа.
Второе условие языка <tex>L</tex> обеспечивает, что <tex>L</tex> — нерегулярный, то есть в нем бесконечное число строк, которые принадлежат <tex>L</tex>, но не могут быть получены путям разрастания некоторой меньшей строки в <tex>L</tex>.
