Formalni jezik
Izvor: Wikipedija
U matematici, logici i računarstvu, formalni jezik 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.
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 sintaktički ispravnih programa u danom programskom jeziku; ili
- skup svih ulaza za koje Turingov stroj staje
[uredi] Specifikacija
Formalni 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.
[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 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
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 pogledati
- 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
[uredi] Dodatna literatura
- Hopcroft, J. & Ullman, J. (1979). Introduction to Automata Theory, Languages, and Computation, Addison-Wesley. ISBN 0-201-02988-X.
- Helena Rasiowa and Roman Sikorski (1970). The Mathematics of Metamathematics, 3rd ed., PWN., 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-9.
- Siniša Srbljić (2003). Jezični procesori 1, Element. ISBN 953-197-129-3.
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. |