Formalni jezik
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.
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 sintaktički ispravnih programa u danom programskom jeziku; ili
- skup svih ulaza za koje Turingov stroj staje
Specifikacija
urediFormalni jezik može biti specificiran na jako mnogo načina, kao npr.
- Nizovi znakova (stringovi) koje generira neka formalna gramatika (pogledati Chomskyevu hijerarhiju jezika);
- Nizovi znakova opisani regularnim izrazom;
- Nizovi znakova koje prihvaća neki automat, poput Turingovog stroja 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 kvocijent 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 s 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 pogledati
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čunala
Izvori
uredi- ↑ Kiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 399
- Hopcroft, J. & Ullman, J. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-XCS1 održavanje: više imena: authors list (link)
- Helena Rasiowa and Roman Sikorski. 1970. The Mathematics of Metamathematics. 3rd ed. izdanje. PWN
|edition=
sadrži dodatni tekst (pomoć), poglavlje 6 Algebra of formalized languages.
- Rozemberg, G. & Salomaa, A. (eds.). 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 978-3-540-61486-9CS1 održavanje: više imena: authors list (link) CS1 održavanje: dodatni tekst: authors list (link)
- Siniša Srbljić. 2003. Jezični procesori 1. Element. ISBN 953-197-129-3
- Zdravko Dovedan. 2003. Formalni jezici - sintaksna analiza. Zavod za informacijske studije FF Zagreb. ISBN 953-175-184-6
- Zdravko Dovedan Han (2012). FORMALNI JEZICI I PREVODIOCI - regularni izrazi, gramatike, automati. Element. ISBN 978-953-197-617-6
Teorija automata: formalni jezici i formalne gramatike | |||
---|---|---|---|
Chomskyjeva hijerarhija |
Gramatike | Jezici | Minimalni automat |
Tip 0 | Neograničenih produkcija | Rekurzivno prebrojiv | Turingov stroj |
n/a | (nema uobičajenog imena) | Rekurzivni | Odlučitelj |
Tip 1 | Kontekstno ovisna | Kontekstno ovisni | Linearno ograničen |
n/a | Indeksirana | Indeksirani | Ugniježđenog stoga |
Tip 2 | Kontekstno neovisna | Kontekstno neovisni | Nedeterministički potisni |
n/a | Deterministička kontekstno neovisna | Deterministički kontekstno neovisni | Deterministički potisni |
Tip 3 | Regularna | Regularni | Konačni |
Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije. |