Леммы о разрастании: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Леммы о разрастании''' (''Pumping lemmas'') | '''Леммы о разрастании''' (''Pumping lemmas'') — | ||
следующие две теоремы, выражающие необходимые условия, | следующие две теоремы, выражающие необходимые условия, | ||
предъявляемые к ''регулярным'' и ''бесконтекстным'' | предъявляемые к ''[[регулярный древовидный язык|регулярным]]'' и ''бесконтекстным'' | ||
языкам. | языкам. | ||
Пусть <math>L</math> | Пусть <math>\,L</math> — ''[[регулярные множества|регулярное множество]]''. Существует такая | ||
константа <math>k</math>, что если <math>\omega \in L</math> и <math>\mid \omega \mid | константа <math>\,k</math>, что если <math>\omega \in L</math> и <math>\mid \omega \mid | ||
\geq k</math>, то цепочку <math>\omega</math> можно представить в виде <math>xyz</math>, | \geq k</math>, то [[цепочка|цепочку]] <math>\,\omega</math> можно представить в виде <math>\,xyz</math>, | ||
где <math>0< \mid y \mid \leq k</math> и <math>xy^{i}z \in L</math> для всех <math>i | где <math>0< \mid y \mid \leq k</math> и <math>xy^{i}z \in L</math> для всех <math>i | ||
\geq 0</math>. | \geq 0</math>. | ||
Для любого ''контекстно-свободного языка'' <math>L</math> существуют | Для любого ''[[контекстно-свободный язык|контекстно-свободного языка]]'' <math>\,L</math> существуют | ||
такие целые <math>l</math> и <math>k</math>, что любая цепочка <math>\alpha</math> из | такие целые <math>\,l</math> и <math>\,k</math>, что любая цепочка <math>\,\alpha</math> из | ||
<math>L,\mid\alpha \mid >l</math>, представима в виде <math>\alpha = uvwxy</math>, | <math>L,\mid\alpha \mid >l</math>, представима в виде <math>\,\alpha = uvwxy</math>, | ||
где | где | ||
| Строка 21: | Строка 21: | ||
(3) <math>uv^iwx^iy\in L</math> для любого <math>i\geq 0</math>. | (3) <math>uv^iwx^iy\in L</math> для любого <math>i\geq 0</math>. | ||
==Литература== | ==Литература== | ||
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. --- Т. 1,2. | |||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | |||
* Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991. | |||
Текущая версия от 13:10, 29 апреля 2011
Леммы о разрастании (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.