Formalni jezik

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 riječ (string, niz znakova) nad tim alfabetom može biti .

Tipični jezik nad abecedom, koji sadrži tu riječ, bi bio skup svih riječi koje sadrže isti broj znakova  and .

Prazan niz (ili prazna riječ) je riječ dužine 0, i često se označava znakom ,  ili . 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 
 skup , gdje je  prirodan broj i  znači  ponavljano  puta 
 Konačni jezici, kao što su  
 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  i  jezici nad nekom uobičajenom abecedom.
 Nadovezivanje (ili konkatenacija)  se sastoji od svih nizova znakova oblika  gdje je  niz znakova iz  i  niz znakova iz .
 Presjek  jezika  i jezika  se sastoji od svih nizova znakova koji su sadržani i u  i u .
 Unija  jezika  i jezika  se sastoji od svih nizova znakova koji su sadržani ili u  ili u .
 Komplement  jezika  se sastoji od svih nizova znakova nad abecedom koji nisu sadržani u .
 Desni koeficijent  jezika  jezikom  se sastoji od svih nizova znakova  za koje postoji niz znakova  u  takav da je  u jeziku .
 Kleeneov operator  se sastoji od svih nizova znakova koji mogu biti zapisani u obliku  sa nizovima znakova  u  i . Uočite da ovo uključuje prazni niz  pošto je dozvoljen .
 Prevrtanje  se sastoji od preokrenutih verzija svih nizova znakova u .
 Miješanje (engl. shuffle) jezika  i  se sastoji od svih nizova znakova koji mogu biti zapisani u obliku  gdje je  i  su nizovi znakova takvi da nadovezivanje  je u jeziku  i  su nizovi znakova takvi da je  u jeziku .

 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; 
 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; 
 Siniša Srbljić - Jezični procesori 1, Element, 2003;