177
правок
Изменения
→Пример нерегулярного языка, для которого выполняется лемма о разрастании
== Пример нерегулярного языка, для которого выполняется лемма о разрастании==
===Пример языка, удовлетворяющего стандартной версии леммы===
Рассмотрим следующий язык: <tex>L= \{ a^{i}b^{j}c^{k} \mid i \ne 1, j \geqslant 0, k \geqslant 0\} \cup \{ ab^{i}c^{i} \mid i \geqslant 1\}</tex>
'''Таким образом''', язык <tex> L </tex> удовлетворяет второй части леммы и при этом является нерегулярным, что доказывает тот факт, что лемма о разрастании '''не''' является достаточным для регулярности языка.
===Пример языка, удовлетворяющего лемме в общем виде===
Рассмотрим другой пример.
<tex>L = L_1 \cup L_2</tex>
'''Докажем, что он нерегулярный.''' Предположим, что некоторая строка языка <tex>L</tex> имеет длину пять. Поскольку в алфавите всего четыре символа, то как минимум два символа из пяти в этой строке будут одинаковыми, и они разделены максимум тремя символами:
:Если дубликаты разделены нулями или единицами, накачаем один из двух остальных символов в строке, которые не повлияют на подстроку, которая содержит дубликаты,
:Если дубликаты разделены двойками или тройками, накачаем 2 символа, разделяющих их. Накачка также уменьшает или увеличивает результат во время создания подстроки размера 3, которая содержит 2 продублированных символа
