დატუმბვის ლემა რეგულარული ენებისთვის: განსხვავება გადახედვებს შორის
| [შეუმოწმებელი ვერსია] | [შეუმოწმებელი ვერსია] |
შიგთავსი ამოიშალა შიგთავსი დაემატა
No edit summary |
No edit summary |
||
ხაზი 1:
'''დატუმბვის ლემა რეგულარული
▲'''დატუმბვის ლემა რეგულარული ენებითვის''' — [[ლემა]] [[ფორმალური ენები]]ს თეორიაში. აღწერს რეგულარული ენის აუცილებელ თვისებას: საკმარისად გრძელი ყველა სიტყვა არის „დატუმბვადი“, ანუ გააჩნია შუა ნაწილი, რომლის ნებისმიერ რაოდენობაჯერ განმეორების შემთხვევაში მიიღება იმავე ენის სხვა სიტყვა. იმის ჩვენებით, რომ ვიეთ ენას არ აქვს ეს თვისება, მტკიცდება მისი არარეგულარულობა. გამოიყენება უსასრულოდ დიდი ენებისათვის.
ლემის მიხედვით, ნებისმიერი რეგულარული <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>
== ფორმალური ჩანაწერი ==
Line 11 ⟶ 10:
* <math> (\forall n \geq 0) ( xy^nz \in L )</math>
თუკი სრულდება მოცემული პირობები, მაშინ <math>y</math> ქვესტრიქონი იტუმბება (რამდენჯერმე განმეორებით ან წაშლით მიღებული სიტყვა რჩება <math>L</math> ენაში). <math>x</math> და <math>z</math> ქვესტრინგების სიგრძეების არ არის შეზღუდული და შეიძლება <math>0</math>-იც იყოს.
ლემა მთლიანად ფორმალურ ენაზე:
Line 26 ⟶ 25:
== ლემის გამოყენება ==
ლემის გამოყენება ხდება საწინააღმდეგოს დაშვების მეთოდით
მაგალითად, <math>\Sigma = \{a, b\}</math> ანბანისაგან შედგენილი <math>L = \{a^n b^n : n \geq 0\}</math> ენის არარეგულარობა მტკიცდება შემდეგნაირად.▼
▲მაგალითად, <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 ენა არაა რეგულარული.▼
▲ცვლადებს ჰქონდეს იგივე მნიშვნელობა, რაც ზემოთ. განვიხილოთ <math>w = a^p b^p</math> სიტყვები (შედის <math>p</math>-ზე გრძელ სიტყვებში). ლემის მიხედვით თუ ენა რეგულარულია უნდა არსებობდეს <math>w = xyz</math> დაყოფა (<math> |y| \geq 1 </math> და <math> |xy| \leq p </math> პირობებით) რომლისთვისაც ყველა <math>xy^iz</math> (<math>i \geq 0</math>) რჩება <math>L</math> ენაში. <math>x</math>-ზე და <math>xy</math>-ზე დაწესებული შეზღუდვებიდან გამომდინარეობს, რომ <math>y</math> მხოლოდ <math>a</math>-ებს შეიცავს. შესაბამისად <math>y</math> ნაწილის დატუმბვით მიღებულ სიტყვაში მეტი <math>a</math> იქნება და აღებული ენის პირობას აღარ დააკმაყოფილებს. მაშასადამე <math>L</math> ენა არაა რეგულარული.
==ლიტერატურა==
* {{წიგნი|ავტორი=Michael Sipser|სათაური=Introduction to the theory of computation|წელი=2005|გამომცემლობა=Cengage Learning|გვერდები=77-82}}
| |||