Formalni jezik
Sa Wikipedije, slobodne enciklopedije
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:
- 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
.
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.
Sadržaj |
[uredi] 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 sintaksički ispravnih programa u datom programskom jeziku; ili
- skup svih ulaza za koje Turingova mašina staje
[uredi] 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.
[uredi] 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
.
[uredi] Također pogledajte
- 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čunara
[uredi] Dodatna literatura
- Hopcroft, J. & Ullman, J. - Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979; ISBN 0-201-02988-X
- Helena Rasiowa and Roman Sikorski - The Mathematics of Metamathematics, PWN, 1970, poglavlje 6 Algebra of formalized languages.
- Rozemberg, G. & Salomaa, A. (eds.) - Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979; ISBN 978-3-540-61486-9
- Siniša Srbljić - Jezični procesori 1, Element, 2003; ISBN 953-197-129-3