Formalni jezik
Ovaj članak ili neki od njegovih odlomaka nije dovoljno potkrijepljen izvorima (literatura, veb-sajtovi ili drugi izvori). |
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.
Primjeri
urediNeki 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
Specifikacija
urediFormalni 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
urediNekoliko 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 .
Također pogledajte
uredi- 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
Dodatna literatura
uredi- 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