# Formalni jezik

### Izvor: Wikipedija

U matematici, logici i računarstvu, formalni jezik 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.

## [uredi] Primjeri

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

## [uredi] Specifikacija

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

- Nizovi znakova (stringovi) koje generira neka formalna gramatika (pogledati Chomskyevu hijerarhiju jezika);
- Nizovi znakova opisani regularnim izrazom;
- Nizovi znakova koje prihvaća neki automat, poput Turingovog stroja 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 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 .

## [uredi] Također pogledati

- 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čunala

## [uredi] Dodatna literatura

- 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., 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.

Dobavljeno iz "http://hr.wikipedia.org../../../f/o/r/Formalni_jezik.html"

Kategorija: Formalni jezici

##### Views

- Članak
- Razgovor
- Trenutna inačica

##### Traži

##### Drugi jezici

- العربية
- Български
- Bosanski
- Česky
- Dansk
- Deutsch
- Ελληνικά
- English
- Español
- Suomi
- Français
- עברית
- Magyar
- Italiano
- 日本語
- 한국어
- Nederlands
- Polski
- Português
- Română
- Русский
- Slovenčina
- Türkçe
- 中文