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