177
правок
Изменения
→Лемма о разрастании в общем виде
== Лемма о разрастании в общем виде ==
{{Лемма|id= ==lemma==|about=о разрастании, о накачке в общем виде|statement=
Если язык <tex>L</tex> является регулярным, то существует число <tex>p \geqslant 1</tex> такое что для любого слова <tex>uwv</tex> из языка <tex>L</tex>, где <tex>|w| \geqslant p</tex> может быть записано в форме <tex>uwv = uxyzv</tex>,
где слова <tex>x</tex>, <tex>y</tex> и <tex>z</tex> такие, что <tex>|xy| \leqslant p</tex>, <tex>|y| \geqslant 1</tex> и <tex>uxy^izv</tex> принадлежит языку <tex>L</tex> для любого целого числа <tex>i \geqslant 0</tex>.
|proof=
Исходя из формулировки леммы в общем виде, стандартная версия леммы, которая описана выше, является особым случаем, в котором строки <tex>u</tex> и <tex>v</tex> пусты.
Доказательство леммы в общем виде аналогично доказательству стандартной версии леммы, с тем отличием, что строки <tex>u</tex> и <tex>v</tex> теперь могут быть как не пусты, так и пусты.
== Использование леммы для доказательства нерегулярности языков ==
