177
правок
Изменения
Нет описания правки
}}
'''Замечание.''' Условие леммы не является достаточным для регулярности языка. ''(См. [[#Пример нерегулярного языка, для которого выполняется лемма о разрастании|пример]])''
== Лемма о разрастании в общем виде ==
Если язык <tex>L</tex> является регулярным, то существует число <tex>p \ge 1</tex> такое что для любого слова <tex>uwv</tex> из языка <tex>L</tex>, где <tex>|w| \ge p</tex> может быть записано в форме <tex>uwv = uxyzv</tex>,
где слова <tex>x</tex>, <tex>y</tex> и <tex>z</tex> такие, что <tex>|xy| \le p</tex>, <tex>|y| \ge 1</tex> и <tex>uxy^izv</tex> принадлежит языку <tex>L</tex> для любого целого числа <tex>i \ge 0</tex>.
Исходя из этого, стандартная версия леммы, которая описана выше, является особым случаем, в котором строки <tex>u</tex> и <tex>v</tex> пусты.
Поскольку лемма в общем виде накладывает более жесткие требования на язык, то она может быть использована для доказательства нерегулярности многих других языков, таких как <tex> L =\{ a^mb^nc^n : m \ge 1 , n \ge 1 \}</tex>.
== Использование леммы для доказательства нерегулярности языков ==
