U matematici, logici i računarstvu, formalni jezik se sastoji od skupa konačnih nizova 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 .

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

Primjeri

uredi

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 sintaksički ispravnih programa u datom programskom jeziku; ili
  • skup svih ulaza za koje Turingova mašina staje

Specifikacija

uredi

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

Operacije

uredi

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 koeficijent   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 pogledajte

uredi

Dodatna literatura

uredi
  • 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