Formalni jezik

Sa Wikipedije, slobodne enciklopedije

U matematici, logici i računarstvu, formalni jezik $\boldsymbol{L}$ se sastoji od skupa konačnih nizova elemenata konačnog skupa $\boldsymbol{A}$ znakova (simbola). Matematički, to je neuređen par $\boldsymbol{L}=\{\boldsymbol{A},\boldsymbol{F}\}.$ 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 $\boldsymbol{A}$ se zove abeceda jezika $\boldsymbol{L}$ , a elementi skupa $\boldsymbol{F}$ se zovu riječi. U drugom slučaju, skup $\boldsymbol{A}$ se zove leksikon ili vokabular skupa $\boldsymbol{F}$ , dok se elementi skupa $\boldsymbol{F}$ 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 $\left \{ a , b \right \}$ , a riječ (string, niz znakova) nad tim alfabetom može biti $ababba\,$ .

Tipični jezik nad abecedom, koji sadrži tu riječ, bi bio skup svih riječi koje sadrže isti broj znakova $a\,$ and $b\,$ .

Prazan niz (ili prazna riječ) je riječ dužine 0, i često se označava znakom $e\,$ , $\epsilon\,$ ili $\Lambda\,$ . 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.

[uredi] Primjeri

Neki primjeri formalnih jezika:

skup svih riječi nad ${a, b}\,$
skup $\left \{ a^{n}\right\}$ , gdje je $n\,$ prirodan broj i $a^n\,$ znači $a\,$ ponavljano $n\,$ puta
Konačni jezici, kao što su $\{\{a,b\},\{a, aa, bba\}\}\,$
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 $\boldsymbol{L}_{1}$ i $\boldsymbol{L}_{2}$ jezici nad nekom uobičajenom abecedom.

Nadovezivanje (ili konkatenacija) $\boldsymbol{L}_{1}\boldsymbol{L}_{2}\,$ se sastoji od svih nizova znakova oblika $vw\,$ gdje je $v\,$ niz znakova iz $\boldsymbol{L}_{1}\,$ i $w\,$ niz znakova iz $\boldsymbol{L}_{2}\,$ .
Presjek $\boldsymbol{L}_1 \cap \boldsymbol{L}_2$ jezika $\boldsymbol{L}_{1}\,$ i jezika $\boldsymbol{L}_{2}\,$ se sastoji od svih nizova znakova koji su sadržani i u $\boldsymbol{L}_{1}\,$ i u $\boldsymbol{L}_{2}\,$ .
Unija $\boldsymbol{L}_1 \cup \boldsymbol{L}_2$ jezika $\boldsymbol{L}_{1}\,$ i jezika $\boldsymbol{L}_{2}\,$ se sastoji od svih nizova znakova koji su sadržani ili u $\boldsymbol{L}_{1}\,$ ili u $\boldsymbol{L}_{2}\,$ .
Komplement $\complement \boldsymbol{L}_{1}\,$ jezika $\boldsymbol{L}_{1}\,$ se sastoji od svih nizova znakova nad abecedom koji nisu sadržani u $\boldsymbol{L}_{1}\,$ .
Desni koeficijent $\boldsymbol{L}_{1}/\boldsymbol{L}_{2}\,$ jezika $\boldsymbol{L}_{1}\,$ jezikom $\boldsymbol{L}_{2}\,$ se sastoji od svih nizova znakova $v\,$ za koje postoji niz znakova $w\,$ u $\boldsymbol{L}_{2}\,$ takav da je $vw\,$ u jeziku $\boldsymbol{L}_{1}$ .
Kleeneov operator $\boldsymbol{L}_{1}^{*}$ se sastoji od svih nizova znakova koji mogu biti zapisani u obliku $w_{1}w_{2}...w_{n}\,$ sa nizovima znakova $w_{i}\,$ u $\boldsymbol{L}_{1}\,$ i $n \ge 0$ . Uočite da ovo uključuje prazni niz $\epsilon\,$ pošto je dozvoljen $n = 0\,$ .
Prevrtanje $\boldsymbol{L}_{1}^{R}\,$ se sastoji od preokrenutih verzija svih nizova znakova u $\boldsymbol{L}_{1}\,$ .
Miješanje (engl. shuffle) jezika $\boldsymbol{L}_{1}\,$ i $\boldsymbol{L}_{2}\,$ se sastoji od svih nizova znakova koji mogu biti zapisani u obliku $v_{1}w_{1}v_{2}w_{2}\dots v_{n}w_{n}$ gdje je $n \ge 1$ i $v_{1},\dots,v_{n}\,$ su nizovi znakova takvi da nadovezivanje $v_{1}\dots v_{n}$ je u jeziku $\boldsymbol{L}_{1}\,$ i $w_{1},\dots,w_{n}$ su nizovi znakova takvi da je $w_{1}\dots w_{n}$ u jeziku $\boldsymbol{L}_{2}$ .

[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

Preuzeto sa: "http://bs.wikipedia.org../../../f/o/r/Formalni_jezik.html"

Kategorije: Formalni jezici