დატუმბვის ლემა რეგულარული ენებისთვის

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

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

ფორმალური ჩანაწერი

$L$ იყოს რეგულარული ენა. მაშინ არსებობს რიცხვი $p>1$ (დამოკიდებული მხოლოდ $L$-ზე) და $L$-ის $p$-ზე გრძელი ყველა სიტყვა $w$ ჩაიწერება $xyz$ ქვესტრიქონების მიმდევრობად ისე რომ:

• $|y|\geq 1$
• $|xy|\leq p$
• $(\forall n\geq 0)(xy^{n}z\in L)$

თუკი სრულდება მოცემული პირობები, მაშინ $y$ ქვესტრიქონი იტუმბება (რამდენჯერმე განმეორებით ან წაშლით მიღებული სიტყვა რჩება $L$ ენაში). $x$ და $z$ ქვესტრინგების სიგრძეების არ არის შეზღუდული და შეიძლება $0$-იც იყოს.

ლემა მთლიანად ფორმალურ ენაზე:

${\begin{array}{l}(\forall L\subseteq \Sigma ^{*})\\\quad ({\mbox{regular}}(L)\Rightarrow \\\quad ((\exists p\geq 1)((\forall w\in L)((|w|\geq p)\Rightarrow \\\quad ((\exists x,y,z\in \Sigma ^{*})(w=xyz\land (|y|\geq 1\land |xy|\leq p\land (\forall n\geq 0)(xy^{n}z\in L))))))))\end{array}}$

ლემის გამოყენება

ლემის გამოყენება ხდება საწინააღმდეგოს დაშვების მეთოდით რაიმე ენის არარეგულარობის დამტკიცებისას.

მაგალითად, $\Sigma =\{a,b\}$ ანბანისაგან შედგენილი $L=\{a^{n}b^{n}:n\geq 0\}$ ენის არარეგულარობა მტკიცდება ასე:

ცვლადებს ჰქონდეს იგივე მნიშვნელობა, რაც ზემოთ. განვიხილოთ $w=a^{p}b^{p}$ სიტყვები (შედის $p$-ზე გრძელ სიტყვებში). ლემის მიხედვით თუ ენა რეგულარულია უნდა არსებობდეს $w=xyz$ დაყოფა ($|y|\geq 1$ და $|xy|\leq p$ პირობებით) რომლისთვისაც ყველა $xy^{i}z$ ($i\geq 0$) რჩება $L$ ენაში. $x$-ზე და $xy$-ზე დაწესებული შეზღუდვებიდან გამომდინარეობს, რომ $y$ მხოლოდ $a$-ებს შეიცავს. შესაბამისად $y$ ნაწილის დატუმბვით მიღებულ სიტყვაში მეტი $a$ იქნება და აღებული ენის პირობას აღარ დააკმაყოფილებს. მაშასადამე $L$ ენა არაა რეგულარული.

ლიტერატურა

• Michael Sipser, Introduction to the theory of computation, Cengage Learning, 2005. — გვ. 77-82.