Formalni jezik

Izvor: Wikipedija

U matematici, logici i računarstvu, formalni jezik $\boldsymbol{L}$ se sastoji od skupa konačnih slijedova elemenata konačnog skupa $\boldsymbol{A}$ znakova (simbola). Matematički, to je neuređen par $\boldsymbol{L}=\{\boldsymbol{A},\boldsymbol{F}\}.$ Među najuobičajenijim primjenama, formalni jezik može biti shvaćen kao:

kolekcija riječi

ili

kolekcija rečenica

U prvom slučaju, skup $\boldsymbol{A}$ se zove abeceda jezika $\boldsymbol{L}$ , a elementi skupa $\boldsymbol{F}$ se zovu riječi. U drugom slučaju, skup $\boldsymbol{A}$ se zove leksikon ili vokabular skupa $\boldsymbol{F}$ , dok se elementi skupa $\boldsymbol{F}$ zovu rečenice. Matematička teorija koja se općenito bavi proučavanjem formalnih jezika se zove teorija formalnih jezika.

Kao primjer formalnog jezika, abeceda može biti $\left \{ a , b \right \}$ , a riječ (string, niz znakova) nad tim alfabetom može biti $ababba\,$ .

Tipični jezik nad abecedom, koji sadrži tu riječ, bi bio skup svih riječi koje sadrže isti broj znakova $a\,$ and $b\,$ .

Prazni niz (ili prazna riječ) je riječ duljine 0, i često se označava znakom $e\,$ , $\epsilon\,$ ili $\Lambda\,$ . Iako je abeceda konačan skup i svaka riječ je konačne duljine, jezik može imati beskonačno mnogo riječi (jer duljina riječi koje sadrži ne mora nužno imati gornju granicu).

Često postavljano pitanje o formalnim jezicima jest "koliko je teško odlučiti da li zadan riječ pripada nekom određenom jeziku?" Ovo je područje proučavanja teorije izračunljivosti i teorije složenosti.

[uredi] Primjeri

Neki primjeri formalnih jezika:

skup svih riječi nad ${a, b}\,$
skup $\left \{ a^{n}\right\}$ , gdje je $n\,$ prirodan broj i $a^n\,$ znači $a\,$ ponavljano $n\,$ puta
Konačni jezici, kao što su $\{\{a,b\},\{a, aa, bba\}\}\,$
skup svih sintaktički ispravnih programa u danom programskom jeziku; ili
skup svih ulaza za koje Turingov stroj staje

[uredi] Specifikacija

Formalni jezik može biti specificiran na jako mnogo načina, kao npr.

Nizovi znakova (stringovi) koje generira neka formalna gramatika (pogledati Chomskyevu hijerarhiju jezika);
Nizovi znakova opisani regularnim izrazom;
Nizovi znakova koje prihvaća neki automat, poput Turingovog stroja ili konačnog automata;
Nizovi znakova odlučeni postupkom odluke (skupom odgovarajućih DA/NE pitanja) gdje je odgovor DA.

[uredi] Operacije

Nekoliko operacija iz teorije skupova može biti korišteno za stvaranje novih jezika iz već postojećih. Pretpostavimo da su $\boldsymbol{L}_{1}$ i $\boldsymbol{L}_{2}$ jezici nad nekom uobičajenom abecedom.

Nadovezivanje (ili konkatenacija) $\boldsymbol{L}_{1}\boldsymbol{L}_{2}\,$ se sastoji od svih nizova znakova oblika $vw\,$ gdje je $v\,$ niz znakova iz $\boldsymbol{L}_{1}\,$ i $w\,$ niz znakova iz $\boldsymbol{L}_{2}\,$ .
Presjek $\boldsymbol{L}_1 \cap \boldsymbol{L}_2$ jezika $\boldsymbol{L}_{1}\,$ i jezika $\boldsymbol{L}_{2}\,$ se sastoji od svih nizova znakova koji su sadržani i u $\boldsymbol{L}_{1}\,$ i u $\boldsymbol{L}_{2}\,$ .
Unija $\boldsymbol{L}_1 \cup \boldsymbol{L}_2$ jezika $\boldsymbol{L}_{1}\,$ i jezika $\boldsymbol{L}_{2}\,$ se sastoji od svih nizova znakova koji su sadržani ili u $\boldsymbol{L}_{1}\,$ ili u $\boldsymbol{L}_{2}\,$ .
Komplement $\complement \boldsymbol{L}_{1}\,$ jezika $\boldsymbol{L}_{1}\,$ se sastoji od svih nizova znakova nad abecedom koji nisu sadržani u $\boldsymbol{L}_{1}\,$ .
Desni kvocijent $\boldsymbol{L}_{1}/\boldsymbol{L}_{2}\,$ jezika $\boldsymbol{L}_{1}\,$ jezikom $\boldsymbol{L}_{2}\,$ se sastoji od svih nizova znakova $v\,$ za koje postoji niz znakova $w\,$ u $\boldsymbol{L}_{2}\,$ takav da je $vw\,$ u jeziku $\boldsymbol{L}_{1}$ .
Kleeneov operator $\boldsymbol{L}_{1}^{*}$ se sastoji od svih nizova znakova koji mogu biti zapisani u obliku $w_{1}w_{2}...w_{n}\,$ sa nizovima znakova $w_{i}\,$ u $\boldsymbol{L}_{1}\,$ i $n \ge 0$ . Uočite da ovo uključuje prazni niz $\epsilon\,$ pošto je dozvoljen $n = 0\,$ .
Prevrtanje $\boldsymbol{L}_{1}^{R}\,$ se sastoji od preokrenutih verzija svih nizova znakova u $\boldsymbol{L}_{1}\,$ .
Miješanje (engl. shuffle) jezika $\boldsymbol{L}_{1}\,$ i $\boldsymbol{L}_{2}\,$ se sastoji od svih nizova znakova koji mogu biti zapisani u obliku $v_{1}w_{1}v_{2}w_{2}\dots v_{n}w_{n}$ gdje je $n \ge 1$ i $v_{1},\dots,v_{n}\,$ su nizovi znakova takvi da nadovezivanje $v_{1}\dots v_{n}$ je u jeziku $\boldsymbol{L}_{1}\,$ i $w_{1},\dots,w_{n}$ su nizovi znakova takvi da je $w_{1}\dots w_{n}$ u jeziku $\boldsymbol{L}_{2}$ .

[uredi] Također pogledati

Jezik za jezike općenito
Sintaksa za općenit oblik jezika
Semantika za značenja u jeziku
Prirodni jezik za jezike koji nisu formalni
Programski jezik za primjenu formalnih jezika u programiranju računala

[uredi] Dodatna literatura

Hopcroft, J. & Ullman, J. (1979). Introduction to Automata Theory, Languages, and Computation, Addison-Wesley. ISBN 0-201-02988-X.
Helena Rasiowa and Roman Sikorski (1970). The Mathematics of Metamathematics, 3^rd ed., PWN., poglavlje 6 Algebra of formalized languages.
Rozemberg, G. & Salomaa, A. (eds.) (1979). Introduction to Automata Theory, Languages, and Computation, Addison-Wesley. ISBN 978-3-540-61486-9.
Siniša Srbljić (2003). Jezični procesori 1, Element. ISBN 953-197-129-3.

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.