Koja su tri uvjeta koja moraju biti zadovoljena da bi jezik bio regularan prema Lemi o pumpanju?
Pumping Lemma temeljni je alat u polju teorije računalne složenosti koji nam omogućuje da odredimo je li jezik regularan ili ne. Prema Lemi o pumpanju, da bi jezik bio pravilan, moraju biti zadovoljena tri uvjeta. Ovi uvjeti su sljedeći:
1. Uvjet duljine: Prvi uvjet navodi da za svaki niz u jeziku koji je dovoljno dugačak, postoji dekompozicija niza na tri dijela, u, v i w, tako da je duljina v veća od nule i manje ili jednako konstantnoj vrijednosti, a ulančavanje u, v i w je još uvijek u jeziku. Drugim riječima, jezik mora sadržavati nizove koji se mogu podijeliti u tri dijela, gdje se srednji dio može ponoviti bilo koji broj puta, a rezultirajući niz je još uvijek u jeziku.
2. Uvjet pumpanja: Drugi uvjet navodi da je za bilo koji niz u jeziku koji zadovoljava uvjet duljine, moguće "pumpati" srednji dio niza bilo koji broj puta i još uvijek dobiti niz koji je u jeziku. To znači da ponavljanjem središnjeg dijela rezultirajući niz i dalje mora pripadati jeziku.
3. Uvjet članstva: Treći uvjet navodi da za bilo koji niz u jeziku koji zadovoljava uvjete duljine i pumpanja, mora postojati duljina pumpanja, označena kao p, takva da se može pumpati svaki niz duži od p. To znači da je za nizove duže od duljine pumpanja uvijek moguće pronaći dekompoziciju i ponoviti središnji dio kako bi se dobio niz koji je još uvijek u jeziku.
Da bismo ilustrirali ove uvjete, razmotrimo primjer. Pretpostavimo da imamo jezik L = {0^n1^n | n ≥ 0}, koji se sastoji od nizova 0 iza kojih slijedi isti broj 1. Možemo primijeniti lemu pumpanja da odredimo je li ovaj jezik regularan.
1. Uvjet duljine: Pretpostavimo da je duljina pumpanja p. Promotrimo niz s = 0^p1^p. Ovaj niz možemo rastaviti na tri dijela: u = 0^k, v = 0^l i w = 1^p, gdje je k + l ≤ p i l > 0. Budući da v sadrži samo nule, pumpanje v će rezultirati niz koji sadrži više 0 nego 0, kršeći jezik L. Stoga uvjet duljine nije zadovoljen.
Budući da uvjet duljine nije zadovoljen, možemo zaključiti da je jezik L = {0^n1^n | n ≥ 0} nije regularan prema lemi o pumpanju.
Tri uvjeta koja moraju biti zadovoljena da bi jezik bio regularan prema Lemi o pumpanju su uvjet duljine, uvjet pumpanja i uvjet pripadnosti. Ovi uvjeti pružaju moćan alat za određivanje regularnosti jezika u polju teorije računalne složenosti.
Ostala nedavna pitanja i odgovori u vezi EITC/IS/CCTF Osnove teorije računalne složenosti:
- Jesu li regularni jezici ekvivalentni konačnim automatima?
- Nije li klasa PSPACE jednaka klasi EXPSPACE?
- Je li algoritamski izračunljiv problem problem koji može izračunati Turingov stroj u skladu s Church-Turingovom tezom?
- Koje je svojstvo zatvaranja regularnih jezika kod ulančavanja? Kako se konačni strojevi kombiniraju da predstavljaju uniju jezika koje prepoznaju dva stroja?
- Može li se svaki proizvoljni problem izraziti jezikom?
- Je li P klasa složenosti podskup PSPACE klase?
- Ima li svaki Turingov stroj s više traka ekvivalentan Turingov stroj s jednom vrpcom?
- Koji su izlazi predikata?
- Jesu li lambda račun i Turingovi strojevi izračunljivi modeli koji odgovaraju na pitanje što znači izračunljivost?
- Možemo li dokazati da su Np i P klasa iste pronalaženjem učinkovitog polinomskog rješenja za bilo koji NP potpuni problem na determinističkom TM?
Više pitanja i odgovora pogledajte u Osnovama teorije računalne složenosti EITC/IS/CCTF