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

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

Навигация