Formalni jezik
From Wikipedia, the free encyclopedia
U matematici, logici i računarstvu, formalni jezik (još i umjetni jezik[1]) 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.