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:
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 .
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.
Neki primjeri formalnih jezika:
Formalni jezik može biti specificiran na jako mnogo načina, kao npr.
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.
Seamless Wikipedia browsing. On steroids.