Formalni jezik

Iz Wikipedije, slobodne enciklopedije

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.

Primjeri[uredi - уреди | uredi izvor]

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

Specifikacija[uredi - уреди | uredi izvor]

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

Operacije[uredi - уреди | uredi izvor]

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 pogledati[uredi - уреди | uredi izvor]

Izvori[uredi - уреди | uredi izvor]

  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.