Леммы о разрастании

Леммы о разрастании (Pumping lemmas) - следующие две теоремы, выражающие необходимые условия, предъявляемые к регулярным и бесконтекстным языкам.

Пусть </math>L[math]\displaystyle{ --- ''регулярное множество''. Существует такая константа }[/math]k[math]\displaystyle{ , что если }[/math]\omega \in L[math]\displaystyle{ и }[/math]\mid \omega \mid \geq k[math]\displaystyle{ , то цепочку }[/math]\omega[math]\displaystyle{ можно представить в виде }[/math]xyz[math]\displaystyle{ , где }[/math]0< \mid y \mid \leq k[math]\displaystyle{ и }[/math]xy^{i}z \in L[math]\displaystyle{ для всех }[/math]i \geq 0[math]\displaystyle{ . Для любого ''контекстно-свободного языка'' }[/math]L[math]\displaystyle{ существуют такие целые }[/math]l[math]\displaystyle{ и }[/math]k[math]\displaystyle{ , что любая цепочка }[/math]\alpha[math]\displaystyle{ из }[/math]L,\mid\alpha \mid >l[math]\displaystyle{ , представима в виде }[/math]\alpha = uvwxy[math]\displaystyle{ , где (1) }[/math]\mid vwx\mid \leq k[math]\displaystyle{ ; (2) }[/math]vx\neq e[math]\displaystyle{ ; (3) }[/math]uv^iwx^iy\in L[math]\displaystyle{ для любого }[/math]i\geq 0<math>.

Литература

[Ахо-Ульман],

[Касьянов/95],

[Словарь]