Millised on kolm tingimust, mis peavad olema täidetud, et keel oleks Pumping Lemma järgi korrapärane?
Pumpamislemma on arvutusliku keerukuse teooria põhitööriist, mis võimaldab meil kindlaks teha, kas keel on korrapärane või mitte. Pumping Lemma järgi peab keele regulaarseks olemiseks olema täidetud kolm tingimust. Need tingimused on järgmised:
1. Pikkuse tingimus: esimene tingimus sätestab, et mis tahes stringi puhul keeles, mis on piisavalt pikk, on string jaotatud kolmeks osaks, u, v ja w, nii et v pikkus on suurem kui null ja väiksem või võrdne konstantse väärtusega ning u, v ja w konkatenatsioon on endiselt keeles. Teisisõnu peab keel sisaldama stringe, mida saab jagada kolmeks osaks, kus keskmist osa saab korrata suvalise arvu kordi ja saadud string on endiselt keeles.
2. Pumpamise tingimus: teine tingimus ütleb, et iga keele stringi puhul, mis vastab pikkuse tingimusele, on võimalik stringi keskmist osa "pumbata" suvaline arv kordi ja saada ikkagi string, mis on selles keeles. See tähendab, et keskosa kordamisel peab tekkiv string ikkagi keelele kuuluma.
3. Liikmelisuse tingimus: Kolmas tingimus sätestab, et iga keele stringi jaoks, mis vastab pikkusele ja pumpamise tingimustele, peab olema pumpamispikkus, mida tähistatakse kui p, et saaks pumbata mis tahes stringi, mis on pikem kui p. See tähendab, et pumpamispikkusest pikemate stringide puhul on alati võimalik leida dekompositsioon ja korrata keskmist osa, et saada veel keeles olevat stringi.
Nende tingimuste illustreerimiseks vaatleme näidet. Oletame, et meil on keel L = {0^n1^n | n ≥ 0}, mis koosneb 0-de stringidest, millele järgneb sama arv 1-sid. Saame rakendada Pumping Lemma, et teha kindlaks, kas see keel on regulaarne.
1. Pikkuse tingimus: oletame, et pumpamise pikkus on p. Vaatleme stringi s = 0^p1^p. Saame selle stringi jagada kolmeks osaks: u = 0^k, v = 0^l ja w = 1^p, kus k + l ≤ p ja l > 0. Kuna v sisaldab ainult 0-sid, annab v pumpamine tulemuseks string, mis sisaldab rohkem 0 kui 1, mis rikub keelt L. Seetõttu ei ole pikkuse tingimus täidetud.
Kuna pikkuse tingimus ei ole täidetud, võime järeldada, et keel L = {0^n1^n | n ≥ 0} ei ole pumpamislemma järgi korrapärane.
Kolm tingimust, mis peavad olema täidetud, et keel oleks Pumping Lemma järgi korrapärane, on pikkuse tingimus, pumpamise tingimus ja liikmelisuse tingimus. Need tingimused pakuvad võimsa vahendi keelte regulaarsuse määramiseks arvutusliku keerukuse teooria valdkonnas.
Muud hiljutised küsimused ja vastused selle kohta EITC/IS/CCTF arvutusliku keerukuse teooria alused:
- Palun kirjeldage vastuses näidet, kus on FSM-i tuvastav binaarne string isegi 1 sümboliga." …sisendstring "1011", FSM ei jõua lõppolekusse ja jääb pärast kolme esimese sümboli töötlemist S0-sse kinni."
- Kuidas mõjutab mittedeterminism üleminekufunktsiooni?
- Kas tavakeeled on samaväärsed lõplike olekumasinatega?
- Kas klass PSPACE ei ole võrdne klassiga EXPSPACE?
- Kas algoritmiliselt arvutatav probleem on Church-Turingi teesi kohaselt Turingi masinaga arvutatav probleem?
- Mis on konkatenatsiooni all olevate tavakeelte sulgemisomadus? Kuidas kombineeritakse lõplikke olekumasinaid, et esindada kahe masina poolt tunnustatud keelte ühendust?
- Kas iga suvalist probleemi saab väljendada keelena?
- Kas P keerukusklass on PSPACE klassi alamhulk?
- Kas igal mitme lindiga Turingi masinal on samaväärne ühelindiga Turingi masin?
- Millised on predikaatide väljundid?
Vaadake rohkem küsimusi ja vastuseid EITC/IS/CCTF-i arvutusliku keerukuse teooria põhialustest