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