Formalni jezik

U matematici, logici i računarstvu, formalni jezik (još i umjetni jezik^[1]) ${\displaystyle {\boldsymbol {L}}}$ se sastoji od skupa konačnih slijedova elemenata konačnog skupa ${\displaystyle {\boldsymbol {A}}}$ znakova (simbola). Matematički, to je neuređen par ${\displaystyle {\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 ${\displaystyle {\boldsymbol {A}}}$ se zove abeceda jezika ${\displaystyle {\boldsymbol {L}}}$, a elementi skupa ${\displaystyle {\boldsymbol {F}}}$ se zovu riječi. U drugom slučaju, skup ${\displaystyle {\boldsymbol {A}}}$ se zove leksikon ili vokabular skupa ${\displaystyle {\boldsymbol {F}}}$, dok se elementi skupa ${\displaystyle {\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 ${\displaystyle \left\{a,b\right\}}$, a riječ (string, niz znakova) nad tim alfabetom može biti ${\displaystyle ababba\,}$.

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

Prazni niz (ili prazna riječ) je riječ duljine 0, i često se označava znakom ${\displaystyle e\,}$, ${\displaystyle \epsilon \,}$ ili ${\displaystyle \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 ${\displaystyle {a,b}\,}$
• skup ${\displaystyle \left\{a^{n}\right\}}$, gdje je ${\displaystyle n\,}$ prirodan broj i ${\displaystyle a^{n}\,}$ znači ${\displaystyle a\,}$ ponavljano ${\displaystyle n\,}$ puta
• Konačni jezici, kao što su ${\displaystyle \{\{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 ${\displaystyle {\boldsymbol {L}}_{1}}$ i ${\displaystyle {\boldsymbol {L}}_{2}}$ jezici nad nekom uobičajenom abecedom.

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

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

Izvori

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

• 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. izdanje. PWN |edition= sadrži dodatni tekst (pomoć), 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

• Zdravko Dovedan. 2003. Formalni jezici - sintaksna analiza. Zavod za informacijske studije FF Zagreb. ISBN 953-175-184-6
• Zdravko Dovedan Han (2012). FORMALNI JEZICI I PREVODIOCI - regularni izrazi, gramatike, automati. Element. ISBN 978-953-197-617-6

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.