177
правок
Изменения
→Пример нерегулярного языка, для которого выполняется лемма о разрастании
'''Таким образом''', язык <tex> L </tex> удовлетворяет второй части леммы и при этом является нерегулярным, что доказывает тот факт, что лемма о разрастании '''не''' является достаточным для регулярности языка.
Рассмотрим другой пример.
<tex>L_1 = \{ uvwxy : u, y \in \{ 0,1 ,2,3 \}^*; v,w,x \in \{ 0,1,2,3 \} \wedge ( v = w \vee v = x \vee x =w) \}</tex>
<tex>L_2 = \{ w : w \in \{ 0,1 ,2,3 \}^* \wedge</tex> примерно <tex>\dfrac{1}{7}</tex> из символов слова <tex>w</tex> является символом <tex>3 \} </tex>
<tex>L = L_1 \cup L_2</tex>
Предположим, что некоторая строка языка <tex>L</tex> имеет длину 5. Поскольку в алфавите всего 4 символа, то как минимум два символа из пяти в этой строке будут одинаковыми, и они разделены максимум тремя символами.
== См. также ==
