Formalni jezik

Šablon:Nedostaju izvori U matematici, logici i računarstvu, formalni jezik $𝑳$ se sastoji od skupa konačnih nizova elemenata konačnog skupa $𝑨$ znakova (simbola). Matematički, to je neuređen par $𝑳=\{𝑨,𝑭\}.$ 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 $𝑨$ se zove abeceda jezika $𝑳$, a elementi skupa $𝑭$ se zovu riječi. U drugom slučaju, skup $𝑨$ se zove leksikon ili vokabular skupa $𝑭$, dok se elementi skupa $𝑭$ 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 $\{a,b\}$, 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$, $ϵ$ ili $\mathrm{\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 ${𝑳}_1$ i ${𝑳}_2$ jezici nad nekom uobičajenom abecedom.

• Nadovezivanje (ili konkatenacija) ${𝑳}_1{𝑳}_2$ se sastoji od svih nizova znakova oblika $vw$ gdje je $v$ niz znakova iz ${𝑳}_1$ i $w$ niz znakova iz ${𝑳}_2$.
• Presjek ${𝑳}_1\cap {𝑳}_2$ jezika ${𝑳}_1$ i jezika ${𝑳}_2$ se sastoji od svih nizova znakova koji su sadržani i u ${𝑳}_1$ i u ${𝑳}_2$.
• Unija ${𝑳}_1\cup {𝑳}_2$ jezika ${𝑳}_1$ i jezika ${𝑳}_2$ se sastoji od svih nizova znakova koji su sadržani ili u ${𝑳}_1$ ili u ${𝑳}_2$.
• Komplement $\complement {𝑳}_1$ jezika ${𝑳}_1$ se sastoji od svih nizova znakova nad abecedom koji nisu sadržani u ${𝑳}_1$.
• Desni koeficijent ${𝑳}_1/{𝑳}_2$ jezika ${𝑳}_1$ jezikom ${𝑳}_2$ se sastoji od svih nizova znakova $v$ za koje postoji niz znakova $w$ u ${𝑳}_2$ takav da je $vw$ u jeziku ${𝑳}_1$.
• Kleeneov operator ${𝑳}_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 ${𝑳}_1$ i $n\ge 0$. Uočite da ovo uključuje prazni niz $ϵ$ pošto je dozvoljen $n=0$.
• Prevrtanje ${𝑳}_1^R$ se sastoji od preokrenutih verzija svih nizova znakova u ${𝑳}_1$.
• Miješanje (engl. shuffle) jezika ${𝑳}_1$ i ${𝑳}_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 ${𝑳}_1$ i $w_1,\dots ,w_n$ su nizovi znakova takvi da je $w_1\dots w_n$ u jeziku ${𝑳}_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; Šablon:ISBN
• 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; Šablon:ISBN
• Siniša Srbljić - Jezični procesori 1, Element, 2003; Šablon:ISBN