Formalni jezik

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

Prazan niz (ili prazna riječ) je riječ dužine 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 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 ${\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 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 ${\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 koeficijent ${\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}\,}$ sa 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 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; ISBN 0-201-02988-X
• 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; ISBN 978-3-540-61486-9
• Siniša Srbljić - Jezični procesori 1, Element, 2003; ISBN 953-197-129-3