Леммы о разрастании: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Леммы о разрастании''' (''Pumping lemmas'') - следующие две теоремы, выражающие необ...)
 
Нет описания правки
 
(не показаны 2 промежуточные версии этого же участника)
Строка 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>,
где
где


(1) </math>\mid vwx\mid \leq k<math>;
(1) <math>\mid vwx\mid \leq k</math>;


(2) </math>vx\neq e<math>;
(2) <math>vx\neq e</math>;


(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.
 
[Касьянов/95],  
* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 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.