დატუმბვის ლემა რეგულარული ენებისთვის: განსხვავება გადახედვებს შორის

'''დატუმბვის ლემა რეგულარული ენებითვის''' — [[ლემა]] [[ფორმალური ენები]]ს თეორიაში, რომელიც. აღწერს რეგულარული ენებისენის აუცილებელ თვისებას. ასეთი ენის: საკმარისად გრძელი ყველა სიტყვა არის „დატუმბვადი“, ანუ გააჩნია შუა ნაწილი, რომლის ნებისმიერ რაოდენობაჯერ განმეორების შემთხვევაში მიიღება იმავე ენის სხვა სიტყვა. იმის ჩვენებით, რომ ზოგ ენას არ აქვს ეს თვისება, მტკიცდება მისი არარეგულარულობა. გამოიყენება უსასრულოდ დიდი ენებისათვის.

უფრო კონკრეტულად, ლემის მიხედვით, ნებისმიერი რეგულარული <math>L</math> ენისათვის არსებობს <math>p</math> მუდმივა და ამ ენაში მასზე სიგრძით არამკაცრად დიდი ყველა სიტყვა <math>w</math> დაიყოფა სამ ქვესტრიქონად (<math>w = xyz</math>), ისე, რომ <math>y</math>-ს განმეორებით მიღებული სიტყვები <math>xz, xyz, xyyz, xyyyz, ...</math> მაინც <math>L</math>-ს ეკუთვნის. ეს პროცესი ცნობილია დატუმბვის სახელით. ლემისათის აუცილებელია, რომ <math>xy</math> ქვესტრინგის სიგრძე იყოს მაქსიმუმ <math>p</math>, რაც ამცირებს სიტყვის დაჭრის ვარიანტებს. ყველა სასრული ენა დატუმბვადია და მათთვის <math>p</math> უდრის ენაში უგრძესი სიტყვის სიგრძეზე ერთით მეტს.