4183
правки
Леммы о разрастании: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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>, | ||