# Formalni jezik

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

**Prazan niz** (ili *prazna riječ*) je riječ dužine 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 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

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

## Specifikacija

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

* Nizovi znakova (*stringovi*) koje generiše neka formalna gramatika (pogledati Chomskyevu hijerarhiju jezika);
* Nizovi znakova opisani regularnim izrazom;
* Nizovi znakova koje prihvata neki automat, poput Turingove mašine 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 koeficijent* 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 .

## Također pogledajte

* 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čunara

## Dodatna literatura

* 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