Ovaj članak ili neki od njegovih odlomaka nije dovoljno potkrijepljen
izvorima (literatura, veb-sajtovi ili drugi izvori). Ako se pravilno ne potkrijepe
pouzdanim izvorima, sporne rečenice i navodi mogli bi biti izbrisani. Pomozite Wikipediji tako što ćete navesti validne izvore putem
referenci te nakon toga možete ukloniti ovaj šablon.
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:
ili
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
![{\displaystyle {a,b}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/34d05124d08c4e30262633f5084e50bb8fb60a44)
- skup
, gdje je
prirodan broj i
znači
ponavljano
puta
- Konačni jezici, kao što su
![{\displaystyle \{\{a,b\},\{a,aa,bba\}\}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02fdc385d8e5193bd85f5e1cc227119818722f23)
- 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
.