Koja su tri uslova koja moraju biti zadovoljena da bi jezik bio regularan prema Lemi o pumpanju?
Lema o pumpanju je fundamentalni alat u polju teorije računske složenosti koji nam omogućava da odredimo da li je jezik regularan ili ne. Prema Lemi o pumpanju, da bi jezik bio regularan, moraju biti zadovoljena tri uslova. Ovi uslovi su sledeći:
1. Uslov dužine: Prvi uslov kaže da za bilo koji niz u jeziku koji je dovoljno dugačak, postoji dekompozicija niza na tri dela, u, v i w, tako da je dužina v veća od nule i manje od ili jednako konstantnoj vrijednosti, a konkatenacija u, v i w je još uvijek u jeziku. Drugim riječima, jezik mora sadržavati nizove koji se mogu podijeliti na tri dijela, pri čemu se srednji dio može ponoviti bilo koji broj puta, a rezultirajući niz je još uvijek u jeziku.
2. Uslov pumpanja: Drugi uslov kaže da je za bilo koji string u jeziku koji zadovoljava uslov dužine moguće "pumpati" srednji deo niza bilo koji broj puta i dalje dobiti string koji je u jeziku. To znači da ponavljanjem srednjeg dijela rezultujući niz mora i dalje pripadati jeziku.
3. Uslov članstva: Treći uslov navodi da za bilo koji niz na jeziku koji zadovoljava dužinu i uslove pumpanja, mora postojati dužina pumpanja, označena kao p, tako da bilo koji niz duži od p može biti pumpan. To znači da je za nizove duže od dužine pumpanja uvijek moguće pronaći dekompoziciju i ponoviti srednji dio kako bi se dobio niz koji je još uvijek u jeziku.
Da bismo ilustrovali ove uslove, razmotrimo jedan primer. Pretpostavimo da imamo jezik L = {0^n1^n | n ≥ 0}, koji se sastoji od nizova 0 praćenih istim brojem 1. Možemo primijeniti Lemu o pumpanju da odredimo da li je ovaj jezik regularan.
1. Uslov dužine: Pretpostavimo da je dužina pumpanja p. Razmotrimo 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. Pošto v sadrži samo 0, pumpanje v će rezultirati string koji sadrži više 0 nego 1, kršeći jezik L. Stoga uslov dužine nije zadovoljen.
Pošto uslov dužine nije zadovoljen, možemo zaključiti da je jezik L = {0^n1^n | n ≥ 0} nije regularan prema Lemi o pumpanju.
Tri uslova koja moraju biti zadovoljena da bi jezik bio regularan prema Lemi o pumpanju su uslov dužine, uslov pumpanja i uslov članstva. Ovi uslovi pružaju moćno oruđe za određivanje regularnosti jezika u oblasti teorije računske složenosti.
Ostala nedavna pitanja i odgovori u vezi EITC/IS/CCTF Osnove teorije računske složenosti:
- Da li su regularni jezici ekvivalentni sa konačnim mašinama?
- Zar PSPACE klasa nije jednaka klasi EXPSPACE?
- Da li je algoritamski izračunljiv problem problem koji se može izračunati Turingovom mašinom u skladu sa Church-Turing tezom?
- Koje je svojstvo zatvaranja regularnih jezika pod konkatenacijom? Kako su konačne mašine kombinovane da predstavljaju uniju jezika koje prepoznaju dve mašine?
- Može li se svaki proizvoljni problem izraziti jezikom?
- Da li je P klasa složenosti podskup klase PSPACE?
- Da li svaka Turing mašina sa više traka ima ekvivalentnu Turing mašinu sa jednom trakom?
- Koji su rezultati predikata?
- Da li su lambda račun i Turingove mašine izračunljivi modeli koji odgovara na pitanje šta znači izračunljiv?
- Možemo li dokazati da su Np i P klasa iste pronalaženjem efikasnog polinomskog rješenja za bilo koji NP kompletan problem na determinističkom TM?