# Formalni jezik

U matematici, logici i računarstvu, **formalni jezik** (još i **umjetni jezik**) WIKINIUM\_MATH\_PH\_0 se sastoji od skupa konačnih slijedova elemenata konačnog skupa WIKINIUM\_MATH\_PH\_2 znakova (simbola). Matematički, to je neuređen par WIKINIUM\_MATH\_PH\_4 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 WIKINIUM\_MATH\_PH\_6 se zove *abeceda* jezika WIKINIUM\_MATH\_PH\_8 , a elementi skupa WIKINIUM\_MATH\_PH\_10 se zovu *riječi*. U drugom slučaju, skup WIKINIUM\_MATH\_PH\_12 se zove *leksikon* ili *vokabular* skupa WIKINIUM\_MATH\_PH\_14 , dok se elementi skupa WIKINIUM\_MATH\_PH\_16 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 WIKINIUM\_MATH\_PH\_18 , a riječ (string, niz znakova) nad tim alfabetom može biti WIKINIUM\_MATH\_PH\_20 .

Tipični jezik nad abecedom, koji sadrži tu riječ, bi bio skup svih riječi koje sadrže isti broj znakova WIKINIUM\_MATH\_PH\_22 and WIKINIUM\_MATH\_PH\_24 .

**Prazni niz** (ili *prazna riječ*) je riječ duljine 0, i često se označava znakom WIKINIUM\_MATH\_PH\_26 , WIKINIUM\_MATH\_PH\_28 ili WIKINIUM\_MATH\_PH\_30 . 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 WIKINIUM\_MATH\_PH\_32
* skup WIKINIUM\_MATH\_PH\_34 , gdje je WIKINIUM\_MATH\_PH\_36 prirodan broj i WIKINIUM\_MATH\_PH\_38 znači WIKINIUM\_MATH\_PH\_40 ponavljano WIKINIUM\_MATH\_PH\_42 puta
* Konačni jezici, kao što su WIKINIUM\_MATH\_PH\_44
* 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.

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

## Operacije

Nekoliko operacija iz teorije skupova može biti korišteno za stvaranje novih jezika iz već postojećih. Pretpostavimo da su WIKINIUM\_MATH\_PH\_46 i WIKINIUM\_MATH\_PH\_48 jezici nad nekom uobičajenom abecedom.

* *Nadovezivanje* (ili *konkatenacija*) WIKINIUM\_MATH\_PH\_50 se sastoji od svih nizova znakova oblika WIKINIUM\_MATH\_PH\_52 gdje je WIKINIUM\_MATH\_PH\_54 niz znakova iz WIKINIUM\_MATH\_PH\_56 i WIKINIUM\_MATH\_PH\_58 niz znakova iz WIKINIUM\_MATH\_PH\_60 .
* *Presjek* WIKINIUM\_MATH\_PH\_62 jezika WIKINIUM\_MATH\_PH\_64 i jezika WIKINIUM\_MATH\_PH\_66 se sastoji od svih nizova znakova koji su sadržani i u WIKINIUM\_MATH\_PH\_68 i u WIKINIUM\_MATH\_PH\_70 .
* *Unija* WIKINIUM\_MATH\_PH\_72 jezika WIKINIUM\_MATH\_PH\_74 i jezika WIKINIUM\_MATH\_PH\_76 se sastoji od svih nizova znakova koji su sadržani ili u WIKINIUM\_MATH\_PH\_78 ili u WIKINIUM\_MATH\_PH\_80 .
* *Komplement* WIKINIUM\_MATH\_PH\_82 jezika WIKINIUM\_MATH\_PH\_84 se sastoji od svih nizova znakova nad abecedom koji nisu sadržani u WIKINIUM\_MATH\_PH\_86 .
* *Desni kvocijent* WIKINIUM\_MATH\_PH\_88 jezika WIKINIUM\_MATH\_PH\_90 jezikom WIKINIUM\_MATH\_PH\_92 se sastoji od svih nizova znakova WIKINIUM\_MATH\_PH\_94 za koje postoji niz znakova WIKINIUM\_MATH\_PH\_96 u WIKINIUM\_MATH\_PH\_98 takav da je WIKINIUM\_MATH\_PH\_100 u jeziku WIKINIUM\_MATH\_PH\_102 .
* *Kleeneov operator* WIKINIUM\_MATH\_PH\_104 se sastoji od svih nizova znakova koji mogu biti zapisani u obliku WIKINIUM\_MATH\_PH\_106 sa nizovima znakova WIKINIUM\_MATH\_PH\_108 u WIKINIUM\_MATH\_PH\_110 i WIKINIUM\_MATH\_PH\_112 . Uočite da ovo uključuje prazni niz WIKINIUM\_MATH\_PH\_114 pošto je dozvoljen WIKINIUM\_MATH\_PH\_116 .
* *Prevrtanje* WIKINIUM\_MATH\_PH\_118 se sastoji od preokrenutih verzija svih nizova znakova u WIKINIUM\_MATH\_PH\_120 .
* *Miješanje* (engl. *shuffle*) jezika WIKINIUM\_MATH\_PH\_122 i WIKINIUM\_MATH\_PH\_124 se sastoji od svih nizova znakova koji mogu biti zapisani u obliku WIKINIUM\_MATH\_PH\_126 gdje je WIKINIUM\_MATH\_PH\_128 i WIKINIUM\_MATH\_PH\_130 su nizovi znakova takvi da nadovezivanje WIKINIUM\_MATH\_PH\_132 je u jeziku WIKINIUM\_MATH\_PH\_134 i WIKINIUM\_MATH\_PH\_136 su nizovi znakova takvi da je WIKINIUM\_MATH\_PH\_138 u jeziku WIKINIUM\_MATH\_PH\_140 .

## Povezano

* Jezik
* Sintaksa
* Semantika
* Prirodni jezik
* Programski jezik

## Reference

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