Formalni jezik

U matematici, logici i računarstvu, formalni jezik (još i umjetni jezik^[1]) ${\displaystyle {\boldsymbol {L}}}$ se sastoji od skupa konačnih slijedova 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\,}$.

Prazni niz (ili prazna riječ) je riječ duljine 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 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.

1. ↑ Kiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 399