U matematici, logici i računarstvu, formalni jezik (još i umjetni jezikKiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 399) se sastoji od skupa konačnih slijedova 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 .
Prazni niz (ili prazna riječ) je riječ duljine 0, i često se označava znakom , ili . 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 skup , gdje je prirodan broj i znači ponavljano puta Konačni jezici, kao što su 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 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 kvocijent 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 s 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 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
, poglavlje 6 Algebra of formalized languages.
Zdravko Dovedan Han (2012). FORMALNI JEZICI I PREVODIOCI - regularni izrazi, gramatike, automati. Element.