Formalni jezik

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

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

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

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

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

• 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. 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 

• 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