დატუმბვის ლემა რეგულარული ენებისთვის: განსხვავება გადახედვებს შორის
| [შემოწმებული ვერსია] | [შეუმოწმებელი ვერსია] |
შიგთავსი ამოიშალა შიგთავსი დაემატა
No edit summary |
No edit summary |
||
ხაზი 1:
{{მუშავდება|1=[[სპეციალური:Contributions/Ercwlff|Ercwlff]]|2=2020 წლის 27 მარტი}}
'''დატუმბვის ლემა რეგულარული ენებითვის''' — [[ლემა]] [[ფორმალური ენები]]ს თეორიაში. აღწერს რეგულარული ენის აუცილებელ თვისებას: საკმარისად გრძელი ყველა სიტყვა არის „დატუმბვადი“, ანუ გააჩნია შუა ნაწილი, რომლის ნებისმიერ რაოდენობაჯერ განმეორების შემთხვევაში მიიღება იმავე ენის სხვა სიტყვა. იმის ჩვენებით, რომ
ლემის მიხედვით, ნებისმიერი რეგულარული <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> უდრის ენაში უგრძესი სიტყვის სიგრძეზე ერთით მეტს.
== ფორმალური ჩანაწერი ==
<math>L</math> იყოს რეგულარული ენა. მაშინ არსებობს რიცხვი <math>p > 1</math> (დამოკიდებული მხოლოდ <math>L</math>-ზე) და <math>L</math>-ის <math>p</math>-ზე გრძელი ყველა სიტყვა <math>w</math> ჩაიწერება <math>xyz</math> ქვესტრიქონების მიმდევრობად ისე რომ:
* <math> |y| \geq 1 </math>
ხაზი 11:
* <math> (\forall n \geq 0) ( xy^nz \in L )</math>
თუკი სრულდება მოცემული პირობები, მაშინ y ქვესტრიქონი იტუმბება (რამდენჯერმე განმეორებით ან წაშლით მიღებული სიტყვა რჩება <math>L</math> ენაში). <math>x</math> და <math>z</math> ქვესტრინგების სიგრძეების არ არის შეზღუდული და შეიძლება <math>0</math>-იც იყოს.
ლემა მთლიანად ფორმალურ ენაზე:
ხაზი 26:
== ლემის გამოყენება ==
ლემის გამოყენება ხდება საწინააღმდეგოს დაშვების მეთოდით რომელიმე ენის არარეგულარობის დამტკიცებისას.
მაგალითად, <math>\Sigma = \{a, b\}</math> ანბანისაგან შედგენილი <math>L = \{a^n b^n : n \geq 0\}</math> ენის არარეგულარობა მტკიცდება შემდეგნაირად.
ცვლადებს ჰქონდეს იგივე მნიშვნელობა, რაც ზემოთ. განვიხილოთ <math>w = a^p b^p</math> სიტყვები (შედის <math>p</math>-ზე გრძელ სიტყვებში). ლემის მიხედვით თუ ენა რეგულარულია უნდა არსებობდეს w = xyz დაყოფა (<math> |y| \geq 1 </math> და <math> |xy| \leq p </math> პირობებით) რომლისთვისაც ყველა <math>xy^iz</math> (<math>i \geq 0</math>) რჩება <math>L</math> ენაში. x-ზე და xy-ზე დაწესებული შეზღუდვებიდან გამომდინარეობს, რომ y მხოლოდ a-ებს შეიცავს. შესაბამისად y ნაწილის დატუმბვით მიღებულ სიტყვაში მეტი a იქნება და აღებული ენის პირობას აღარ დააკმაყოფილებს. მაშასადამე L ენა არაა რეგულარული.
==ლიტერატურა==
| |||