Otvori glavni meni

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.

Sadržaj/Садржај

PrimjeriUredi / Уреди

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

SpecifikacijaUredi / Уреди

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

OperacijeUredi / Уреди

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  .

Također pogledatiUredi / Уреди

IzvoriUredi / Уреди

  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. izd.). 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.