Formalni jezik

Izvor: Hrvatska internetska enciklopedija
Skoči na:orijentacija, traži

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

Tipični jezik nad abecedom, koji sadrži tu riječ, bi bio skup svih riječi koje sadrže isti broj znakova [math]\displaystyle{ a\, }[/math] and [math]\displaystyle{ b\, }[/math].

Prazni niz (ili prazna riječ) je riječ duljine 0, i često se označava znakom [math]\displaystyle{ e\, }[/math], [math]\displaystyle{ \epsilon\, }[/math] ili [math]\displaystyle{ \Lambda\, }[/math]. 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

Neki primjeri formalnih jezika:

  • skup svih riječi nad [math]\displaystyle{ {a, b}\, }[/math]
  • skup [math]\displaystyle{ \left \{ a^{n}\right\} }[/math], gdje je [math]\displaystyle{ n\, }[/math] prirodan broj i [math]\displaystyle{ a^n\, }[/math] znači [math]\displaystyle{ a\, }[/math] ponavljano [math]\displaystyle{ n\, }[/math] puta
  • Konačni jezici, kao što su [math]\displaystyle{ \{\{a,b\},\{a, aa, bba\}\}\, }[/math]
  • skup svih sintaktički ispravnih programa u danom programskom jeziku; ili
  • skup svih ulaza za koje Turingov stroj staje

Specifikacija

Formalni jezik može biti specificiran na jako mnogo načina, kao npr.

Operacije

Nekoliko operacija iz teorije skupova može biti korišteno za stvaranje novih jezika iz već postojećih. Pretpostavimo da su [math]\displaystyle{ \boldsymbol{L}_{1} }[/math] i [math]\displaystyle{ \boldsymbol{L}_{2} }[/math] jezici nad nekom uobičajenom abecedom.

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

Također pogledati

Izvori

  1. 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-X 
  • Helena Rasiowa and Roman Sikorski (1970). The Mathematics of Metamathematics (3rd ed. 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 
  • 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.