Regularni jezik

Из Википедије, слободне енциклопедије
(преусмерено са Regularni jezici)

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:

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:

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š[уреди]

Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
 % (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
 % Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
 % Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.