Formalni jezik

U matematici, logici i računarstvu, **formalni jezik** \boldsymbol{L} se sastoji od skupa konačnih nizova 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\,.

**Prazan niz** (ili *prazna riječ*) je riječ dužine 0, i često se označava znakom  e\, ,  \epsilon\,  ili  \Lambda\, . Iako je abeceda konačan skup i svaka riječ je konačne dužine, jezik može imati beskonačno mnogo riječi (jer dužina 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 zadana riječ pripada nekom određenom jeziku?"
Ovo je područje proučavanja teorije računanja i teorije složenosti.

## 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 sintaksički ispravnih programa u datom programskom jeziku; ili
* skup svih ulaza za koje Turingova mašina staje

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

* Nizovi znakova (*stringovi*) koje generiše neka formalna gramatika (pogledati Chomskyevu hijerarhiju jezika);
* Nizovi znakova opisani regularnim izrazom;
* Nizovi znakova koje prihvata neki automat, poput Turingove mašine ili konačnog automata;
* Nizovi znakova odlučeni postupkom odluke (skupom odgovarajućih DA/NE pitanja) gdje je odgovor DA.

## 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 koeficijent* \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}.

## Također pogledajte 
* 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čunara

## Dodatna literatura 
* Hopcroft, J. & Ullman, J. - Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979; 
* Helena Rasiowa and Roman Sikorski - The Mathematics of Metamathematics, PWN, 1970, poglavlje 6 *Algebra of formalized languages*.
* Rozemberg, G. & Salomaa, A. (eds.) - Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979; 
* Siniša Srbljić - Jezični procesori 1, Element, 2003;