Regularni jezik (još i pravilni jezikKiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 785) jest formalni jezik (tj. potencijalno beskonačan skup konačnih slijedova znakova konačne abecede) koji zadovoljava sljedeća istovjetna svojstva: može ga prihvatiti deterministički konačni automat može ga prihvatiti nedeterministički konačni automat može ga prihvatiti alternirajući konačni automat može biti opisan regularnim izrazom može ga generirati regularna gramatika može ga generirati prefiksna gramatika može ga prihvatiti Turingov stroj čija glava samo čita znakove ulazne trake može se definirati u monadičkoj logici drugog reda Regularni jezici nad abecedom Skup svih regularnih jezika nad abecedom Σ je definiran rekurzivno na sljedeći način: Prazni jezik Ø je regularni jezik. Jezik praznog niza { ε } je regularni jezik. Za svaki a ∈ Σ, singleton { a } je regularni jezik. Ako su A i B regularni jezici, tada su A ∪ B (unija), A • B (nadovezivanje) te A* (Kleeneov operator) također regularni jezici. Nijedan drugi jezik nad Σ nije regularan.
Svi konačni jezici su regularni. Ostali tipični primjeri regularnih jezika uključuju jezik koji se sastoji od svih nizova znakova (stringova) nad abecedom {a, b} koji sadrže paran broj znakova a, ili jezik koji se sastoji od svih nizova znakova oblika: nekoliko znakova a nakon kojih slijedi nekoliko znakova b.
Ako jezik nije regularan, tada stroj koji ga prepoznaje mora imati najmanje Ω(log log n) prostora (gdje je n duljina ulaznog niza). Drugim riječima, klasa složenosti DSPACE(o(log log n)) je jednaka klasi regularnih jezika. U praksi je većina neregularnih problema riješiva strojevima koji uzimaju prostor najmanje logaritamske složenosti.
Svojstva zatvorenosti Regularni jezici su zatvoreni nad sljedećim operacijama: To jest, ako su L i P regularni jezici, tada su sljedeći jezici također regularni:
komplement jezika L Kleeneov operator jezika L slika (kodomena) φ(L) jezika L pod homeomorfizmom nadovezivanje (konkatenacija) jezika L i P unija jezika L i P presjek jezika L i P razlika jezika L i P Prevrtanje jezika L POLOVICA(L), skup svih nizova znakova koji čine prvu polovicu nizova znakova u L
Odlučivanje regularnosti jezika
Da bismo locirali regularne jezike u Chomskyjevoj hijerarhiji, možemo prvo primijetiti da je svaki regularni jezik kontekstno neovisan. Obrat ne vrijedi: primjer je jezik koji sadrži jednak broj znakova a i b, koji je neregularan kontekstno neovisan jezik. Za dokaz neregularnosti jezika poput takvog može se koristiti Myhill-Nerode teorem ili svojstvo napuhavanja.
Postoje dva čisto algebarska pristupa prilikom definiranja regularnih jezika. Ako je Σ konačna abeceda i Σ* označava slobodni monoid nad Σ ako se sastoji od svih nizova znakova nad Σ, f : Σ* → M je monoidni homeomorfizam pri čemu je M konačni monoid, S podskup skupa M, i pri tome je skup f −1(S) regularan. Svaki regularni jezik može iznići na ovakav način.
Ako je L neki podskup skupa Σ*, može se definirati relacija ekvivalencije ~ nad Σ* na sljedeći način: u ~ v je definirana na način uw ∈ L ako i samo ako vw ∈ L za svaki w ∈ Σ* Jezik L je regularan ako i samo ako broj klasa ekvivalencije relacije ~ je konačan. Ako je to istina, tada je taj broj jednak broju stanja minimalnog konačnog automata koji prihvaća L.
Konačni jezici Konačni jezici su specifični podskup klase regularnih jezika - oni jezici koji sadrže samo konačan broj riječi. Oni su očito regularni jer se uvijek može napisati regularni izraz koji je unija svih riječi u jeziku.
Izvori
Vanjske poveznice Odsjek za računarstvo na University of Western Ontario: Grail+, http://www.csd.uwo.ca/Research/grail/ . Programski paket za manipuliranje regularnim izrazima, konačnim automatima i konačnim jezicima. Besplatan za nekomercijalnu uporabu. Chalchalero! http://www.ucse.edu.ar/fma/sepa/chalchalero.htm . Besplatan vizualni softver za manipulaciju regularnim izrazima, regularnim gramatikama, konačnim automatima i konačnim jezicima razvijen od strane projekta SEPa! (Universidad Católica de Santiago del Estero)
Kategorija:Formalni jezici