Regularni jezik

U teoretskoj kompjuterskoj nauci, regularni jezik je formalni jezik (tj. neograničen skup nizova simbola iz ograničenog skupa alfabeta) koji zadovoljava sledeće istovetne osobine:

• može biti prihvaćen od strane deterministički određenog automata (mašine)
• može biti prihvaćen od strane nedeterminističkog konačnog automata
• može biti prihvaćen od strane alternirajućeg konačnog automata
• može biti opisan formalnim regularnim izrazom. Obratite pažnju da su svojstva „regularnog izraza“ dostupna od strane mnogih programskih jezika obrazloženi osobinama uz pomoć kojih mogu da prepoznaju jezike koji nisu regularni, te stoga nisu u potpunosti ekvivalentni formalnim regularnim izrazima.
• može biti generisan od strane regularne gramatike
• može biti prihvaćen od strane Tjuringove mašine
• može biti prepoznat od strane nekog ograničeno određenog monoida
• on je prepoznat nekim finalno generisanim monoidom
• on je prethodna verzija podskupa finitnog monoida u homomorfizmu od slobodnog monoida iz svog alfabeta

Regularni jezici izvan nekog alfabeta

Skup regularnih jezika u jednom alfabetu Σ nekog jezika definiše se isključivo na sledeći način:

• prazan jezik Ø je regularni jezik.
• jezik praznog niza { ε } je regularni jezik.
• Za svako a koje pripada skupu Σ singleton od a { a } je regularni jezik.
• Ukoliko su A i B regularni jezici onda su A unija B , A nadovezivanje na B, i A* (Klinijev operator) regularni jezici.
• Nijedan jezik izvan Σ nije regularan jezik.

Svi konačni jezici su regularni. Drugi tipični primeri uključuju sve jezike koji sadrže sve nizove izvan alfabeta {a, b} koji sadrže paran broj a, ili jezik koji se sastoji iz svih nizova forme: nekoliko a je praćeno sa nekoliko b.

Rezultati kompleksnosti

U kompjuterskoj teoriji kompleksnosti (složenosti), kompleksna klasa svih regularnih jezika ponekad se naziva REGULAR ili REG predstavlja isto što i DSPACE(O(1)) problemi koji se mogu rešiti u nepromenljivom prostoru (prostor koji se koristi je nezavisan od ulazne veličine). REGULAR ≠ AC° pošto uključuje problem odlučivanja da li broj 1 bitova (nizova) u inputu je paran ili neparan i ovaj problem nije u AC°¹. S druge strane nije poznato da sadrži AC°.

Ukoliko jezik nije regularan tada automat mora imati najmanje Ω (log log n) prostora da ga prepozna (gde n označava ulaznu veličinu)². Drugim rečima, DSPACE(o(log log n)) predstavlja klasu regularnih jezika. U praksi većina neregularnih problema se rešava pomoću automata koji zahtevaju najmanje logaritmiski prostor.

Svojstva zatvorenosti

Regularni jezici su zatvoreni prilikom sledećih operacija, tj. ako su L i P regularni jezici onda su i sledeći jezici regularni:

• komplement od L
• Klinijev operator L* od L
• slika φ(L) od L pod nizom homeomorfizma
• nadovezivanje jezika L na jezik P
• unija jezika L i P
• presek jezika L i P
• razlika jezika L i P
• suprotnost

Odlučivanje da li je jezik regularan

Prilikom odlučivanja da li je jezik regularan da bi ga smestili u hijerarhiju Čomskog primećujemo da je svaki jezik kontekstno-slobodan. Suprotno od toga npr. jezik koji se sastoji od niza koji ima podjednak broj a i b je kontekstno-slobodan ali nije regularan. Da bi dokazali da jedan ovakav jezik nije regularan koristimo Mihil-Nerodovu teoremu ili lemu o naduvavanju.

Ne postoje dva isključivo algebarska pristupa u definisanju regularnih jezika. Ukoliko je Σ ograničeni alfabet a Σ* označava slobodni monoid izvan Σ koji sadrži sve nizove izvan Σ, f : Σ* → M je monoidni homomorfizam gde je M finitni monoid, S je podskup od M, onda je skup inverznih slika skupa S regularan. Svaki jezik proizilazi na ovaj način.

Ako je L bilo koji podskup od Σ* onda relaciju ekvivalencije ~ (svojevremeno znanu kao sintaksička relacija) definišemo u Σ* kao što sledi: u ~ v je definisano da znači da je

uw Є L ako i samo ako vw Є L za sve w Є Σ*.

Jezik L je regularan ako i samo ako je broj ekvivalentnih klasa od ~ ograničen (Dokaz za ovo se nalazi u članku o sintaksičkom monoidu). Kada je jezik regularan, onda je broj ekvivalentnih klasa jednak broju minimalne deterministički određene automatizacije prihvaćene u L.

Sličan skup tvrdnji može se formulisati za monoid M koji je podskup skupa Σ*. U ovom slučaju, ekvivalentnost izvan M dovodi do koncepta prepoznatljivih jezika.

Finitni (ograničeni) jezici

Poseban podskup u okviru klase regularnih jezika je finitni jezik - oni koji sadrže jedino ograničen broj reči. Oni su očigledno regularni pošto možete napraviti regularni izraz koji predstavlja uniju svih reči u jeziku te je stoga regularan.

Vidi još

• Lema o naduvavanju za regularne jezike