Изменения

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

Навигация