Regularni jezik

Regularni jezik (još i pravilni jezik^[1]) 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 ${\displaystyle {\bar {L}}}$ jezika L
• Kleeneov operator ${\displaystyle L^{*}}$ jezika L
• slika (kodomena) φ(L) jezika L pod homeomorfizmom
• nadovezivanje (konkatenacija) ${\displaystyle L\circ P}$ jezika L i P
• unija ${\displaystyle L\cup P}$ jezika L i P
• presjek ${\displaystyle L\cap P}$ jezika L i P
• razlika ${\displaystyle L-P}$ jezika L i P
• Prevrtanje ${\displaystyle L^{R}}$ 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 ⁻¹(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.