Regularni jezik

Izvor: Wikipedija
Skoči na: orijentacija, traži

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:

Regularni jezici nad abecedom[uredi VE | uredi]

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 AB (unija), AB (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[uredi VE | uredi]

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 \bar{L} jezika L
  • Kleeneov operator L^* jezika L
  • slika (kodomena) φ(L) jezika L pod homeomorfizmom
  • nadovezivanje (konkatenacija) L \circ P jezika L i P
  • unija L \cup P jezika L i P
  • presjek L \cap P jezika L i P
  • razlika L-P jezika L i P
  • Prevrtanje L^R jezika L
  • POLOVICA(L), skup svih nizova znakova koji čine prvu polovicu nizova znakova u L

Odlučivanje regularnosti jezika[uredi VE | uredi]

Da bismo locirali regularne jezike u Chomskyjevoj hijerarhiji, možemo prvo primjetiti 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

uwL ako i samo ako vwL 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[uredi VE | uredi]

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 budući da se uvijek može napisati regularni izraz koji je unija svih riječi u jeziku.

Izvori[uredi VE | uredi]

  1. Kiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 785

Vanjske poveznice[uredi VE | uredi]

  • 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)
Teorija automata: formalni jezici i formalne gramatike
Chomskyjeva
hijerarhija
Gramatike Jezici Minimalni
automat
Tip 0 Neograničenih produkcija Rekurzivno prebrojiv Turingov stroj
n/a (nema uobičajenog imena) Rekurzivni Odlučitelj
Tip 1 Kontekstno ovisna Kontekstno ovisni Linearno ograničen
n/a Indeksirana Indeksirani Ugniježđenog stoga
Tip 2 Kontekstno neovisna Kontekstno neovisni Nedeterministički potisni
n/a Deterministička kontekstno neovisna Deterministički kontekstno neovisni Deterministički potisni
Tip 3 Regularna Regularni Konačni
Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije.