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

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

Пусть [math]\displaystyle{ \,L }[/math] — регулярное множество. Существует такая константа [math]\displaystyle{ \,k }[/math], что если [math]\displaystyle{ \omega \in L }[/math] и [math]\displaystyle{ \mid \omega \mid \geq k }[/math], то цепочку [math]\displaystyle{ \,\omega }[/math] можно представить в виде [math]\displaystyle{ \,xyz }[/math], где [math]\displaystyle{ 0\lt \mid y \mid \leq k }[/math] и [math]\displaystyle{ xy^{i}z \in L }[/math] для всех [math]\displaystyle{ i \geq 0 }[/math].

Для любого контекстно-свободного языка [math]\displaystyle{ \,L }[/math] существуют такие целые [math]\displaystyle{ \,l }[/math] и [math]\displaystyle{ \,k }[/math], что любая цепочка [math]\displaystyle{ \,\alpha }[/math] из [math]\displaystyle{ L,\mid\alpha \mid \gt l }[/math], представима в виде [math]\displaystyle{ \,\alpha = uvwxy }[/math], где

(1) [math]\displaystyle{ \mid vwx\mid \leq k }[/math];

(2) [math]\displaystyle{ vx\neq e }[/math];

(3) [math]\displaystyle{ uv^iwx^iy\in L }[/math] для любого [math]\displaystyle{ i\geq 0 }[/math].

Литература

• Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. --- Т. 1,2.

• Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.

• Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.