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

'''Леммы о разрастании''' (''Pumping lemmas'') -

предъявляемые к ''регулярным'' и ''бесконтекстным''

Пусть </math>L<math> --- ''регулярное множество''. Существует такая

константа </math>k<math>, что если </math>\omega \in L<math> и </math>\mid \omega \mid

\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

\geq 0<math>.

Для любого ''контекстно-свободного языка'' </math>L<math> существуют

такие целые </math>l<math> и </math>k<math>, что любая цепочка </math>\alpha<math> из

</math>L,\mid\alpha \mid >l<math>, представима в виде </math>\alpha = uvwxy<math>,

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

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

(3) </math>uv^iwx^iy\in L<math> для любого </math>i\geq 0<math>.

[Ахо-Ульман],  

 

[Касьянов/95],