Кіріспе
Регулярлы тілдердің қасиеттерін анықтайтын лемма. Формалды тілдер теориясында, регулярлы тілдерге арналған сорғы леммасы – барлық регулярлы тілдердің маңызды қасиеттерін сипаттайтын лемма. Жай тілмен айтқанда, ол регулярлы тілдегі жеткілікті ұзын кез келген тізбекті "сорғылауға" болады – яғни, тізбектің ортаңғы бөлігін кез келген рет қайталау арқылы тілге жататын жаңа тізбек алуға болады. Нақтырақ айтқанда, сорғы леммасы кез келген регулярлы тіл үшін, тізбектің ұзындығы кем дегенде болатын кез келген тізбекті үш кіші тізбекке – , және – (мұнда бос емес) бөлуге болатын тұрақты сан бар екенін айтады, сондай-ақ, нөл немесе одан көп рет қайталанған тізбектер де сол тілге жатады. Бұл қайталау процесі "сорғылау" деп аталады. Сонымен қатар, сорғы леммасы ұзындығы ең көп дегенде болатынын кепілдік береді, бұл бөлу тәсілдеріне шектеу қояды. Шекті сандағы тізбектері бар тілдер, ең үлкен тізбек ұзындығына бір қосып, сорғы леммасын автоматты түрде орындайды. Осылайша, тілдегі нөлдік тізбектердің ұзындығы сорғы леммасынан үлкен болады. Сорғы леммасы нақты бір тілдің регулярлы еместігін дәлелдеу үшін пайдалы. Оны алғаш 1959 жылы Майкл Рабин мен Дана Скотт дәлелдеді, ал 1961 жылы Ехошуа Бар Хиллель, Миша А. Перлс және Эли Шамир контекстсіз тілдерге арналған сорғы леммасын жеңілдету ретінде қайта ашты.
In the theory of formal languages, the pumping lemma for regular languages is a lemma that describes an essential property of all regular languages. Informally, it says that all sufficiently long strings in a regular language may be pumped—that is, have a middle section of the string repeated an arbitrary number of times—to produce a new string that is also part of the language. Specifically, the pumping lemma says that for any regular language there exists a constant such that any string in with length at least can be split into three substrings , and (, with being non empty), such that the strings constructed by repeating zero or more times are still in This process of repetition is known as "pumping". Moreover, the pumping lemma guarantees that the length of will be at most , imposing a limit on the ways in which may be split. Languages with a finite number of strings vacuously satisfy the pumping lemma by having equal to the maximum string length in plus one. By doing so, zero strings in have length greater than
The pumping lemma is useful for disproving the regularity of a specific language in question. It was first proven by Michael Rabin and Dana Scott in 1959, and rediscovered shortly after by Yehoshua Bar Hillel, Micha A. Perles, and Eli Shamir in 1961, as a simplification of their pumping lemma for context free languages.
Ресми мәлімдеме
Болсын, L – тұрақты тіл. Онда L-ге ғана байланысты бүтін сан бар, сонда L-дегі ұзындығы кем дегенде n (бұл "пампалау ұзындығы" деп аталады) болатын кез келген тізбекті (яғни үш кіші тізбекке бөлуге болады) мына түрде жазуға болады: , мұндағы x, y, z кіші тізбектер. Осы шарттар орындалуы керек:
is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in ). (1) means the loop to be pumped must be of length at least one, that is, not an empty string; (2) means the loop must occur within the first characters. must be smaller than (conclusion of (1) and (2)), but apart from that, there is no restriction on and
In simple words, for any regular language , any sufficiently long string (in ) can be split into 3 parts. i. e. , such that all the strings for are also in
Below is a formal expression of the Pumping Lemma.
y – пампаланатын кіші тізбек (көбейтіліп немесе алынып тасталып, нәтижесіндегі тізбек әрқашан L-де болады). (1) пампаланатын бөліктің ұзындығы кем дегенде бір болуы керек, яғни бос тізбек болмауы керек; (2) пампаланатын бөлік алғашқы n таңбаның ішінде болуы керек. n-ден кіші болуы керек, бірақ басқа шектеулер жоқ, және .
is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in ). (1) means the loop to be pumped must be of length at least one, that is, not an empty string; (2) means the loop must occur within the first characters. must be smaller than (conclusion of (1) and (2)), but apart from that, there is no restriction on and
In simple words, for any regular language , any sufficiently long string (in ) can be split into 3 parts. i. e. , such that all the strings for are also in
Below is a formal expression of the Pumping Lemma.
Қарапайым тілмен айтқанда, кез келген тұрақты тіл үшін, кез келген жеткілікті ұзын тізбекті (L-де) 3 бөлікке бөлуге болады, яғни , мұндағы барлық тізбектер L-де болады.
is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in ). (1) means the loop to be pumped must be of length at least one, that is, not an empty string; (2) means the loop must occur within the first characters. must be smaller than (conclusion of (1) and (2)), but apart from that, there is no restriction on and
In simple words, for any regular language , any sufficiently long string (in ) can be split into 3 parts. i. e. , such that all the strings for are also in
Below is a formal expression of the Pumping Lemma.
Төменде Пампалау леммасының формалды түрі келтірілген.
is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in ). (1) means the loop to be pumped must be of length at least one, that is, not an empty string; (2) means the loop must occur within the first characters. must be smaller than (conclusion of (1) and (2)), but apart from that, there is no restriction on and
In simple words, for any regular language , any sufficiently long string (in ) can be split into 3 parts. i. e. , such that all the strings for are also in
Below is a formal expression of the Pumping Lemma.
Сорғылау леммасын дәлелдеу
Кез келген тұрақты тіл үшін сол тілді қабылдайтын шекті күй автоматтары (FSA) бар. Мұндай FSA-дағы күйлер саны есептеледі және бұл сан помпалау ұзындығы ретінде қолданылады. Ұзындығы кем дегенде болатын тізбек үшін, бастапқы күйі және тізбек шығарылған кезде келесі күйлердің тізбегі болады. FSA-да тек күйлер болғандықтан, осы араланған күйлер тізбегінде кем дегенде бір күй қайталанады. Мұндай күйді деп белгілейік. Машинаны күйдің бірінші кездесуінен екінші кездесуіне жеткізетін өтулер қандай да бір тізбекке сәйкес келеді. Бұл тізбек леммада деп аталады, және машина тізбектің бөлігінсіз немесе тізбекті кез келген ретте қайталап сәйкес келсе, лемманың шарттары орындалады. Мысалы, келесі суретте FSA көрсетілген. FSA тізбегін қабылдайды: abcd. Бұл тізбектің ұзындығы кем дегенде күйлер санына тең болғандықтан (яғни, abcd-ні сканерлеу үшін машинаның өтетін күйлердің жалпы саны 5 болады), «көгершін ұясы» принципі бастапқы күй мен келесі төрт араланған күйлер арасында кем дегенде бір қайталанатын күй болуы керек екенін көрсетеді. Бұл мысалда тек қайталанатын күй. bc подтізбегі машинаны күйден басталып, күйде аяқталатын өтулер арқылы өткізетіндіктен, бұл бөлікті қайталауға болады және FSA әлі де тізбекті қабылдайды, нәтижесінде тізбек пайда болады. Балама ретінде, bc бөлігін жоюға болады және FSA әлі де тізбекті қабылдайды, нәтижесінде тізбек ad пайда болады. Помпалау леммасы тұрғысынан, abcd тізбегі a бөлігіне, bc бөлігіне және d бөлігіне бөлінеді. Қосымша ескерту ретінде, берілген тізбектің белгілі бір детерминистік емес шекті автоматқа кез келген күйді қайталамастан қабылдауға болатынын тексеру мәселесі NP-қиын болып табылады.
As a side remark, the problem of checking whether a given string can be accepted by a given nondeterministic finite automaton without visiting any state repeatedly, is NP hard.