Formalni jezik

U matematici, logici i računarstvu, formalni jezik (još i umjetni 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.

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

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.

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\geq 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\geq 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}$.

Povezano

• Jezik
• Sintaksa
• Semantika
• Prirodni jezik
• Programski jezik

Izvori

• 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 (3rd ed. izd.). 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.