Formalni jezik

U matematici, logici i računarstvu, formalni jezik (još i umjetni 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,b\}$, a riječ (string, niz znakova) nad tim alfabetom može biti $ababba$.

Tipični jezik nad abecedom, koji sadrži tu riječ, bi bio skup svih riječi koje sadrže isti broj znakova $a$ and $b$.

Prazni niz (ili prazna riječ) je riječ duljine 0, i često se označava znakom $e$, $ϵ$ ili $\mathrm{\Lambda }$. 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 $a,b$
• skup $\left\{a^n\right\}$, gdje je $n$ prirodan broj i $a^n$ znači $a$ ponavljano $n$ puta
• Konačni jezici, kao što su $\{\{a,b\},\{a,aa,bba\}\}$
• 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 ${𝑳}_1$ i ${𝑳}_2$ jezici nad nekom uobičajenom abecedom.

• Nadovezivanje (ili konkatenacija) ${𝑳}_1{𝑳}_2$ se sastoji od svih nizova znakova oblika $vw$ gdje je $v$ niz znakova iz ${𝑳}_1$ i $w$ niz znakova iz ${𝑳}_2$.
• Presjek ${𝑳}_1\cap {𝑳}_2$ jezika ${𝑳}_1$ i jezika ${𝑳}_2$ se sastoji od svih nizova znakova koji su sadržani i u ${𝑳}_1$ i u ${𝑳}_2$.
• Unija ${𝑳}_1\cup {𝑳}_2$ jezika ${𝑳}_1$ i jezika ${𝑳}_2$ se sastoji od svih nizova znakova koji su sadržani ili u ${𝑳}_1$ ili u ${𝑳}_2$.
• Komplement $\complement {𝑳}_1$ jezika ${𝑳}_1$ se sastoji od svih nizova znakova nad abecedom koji nisu sadržani u ${𝑳}_1$.
• Desni kvocijent ${𝑳}_1/{𝑳}_2$ jezika ${𝑳}_1$ jezikom ${𝑳}_2$ se sastoji od svih nizova znakova $v$ za koje postoji niz znakova $w$ u ${𝑳}_2$ takav da je $vw$ u jeziku ${𝑳}_1$.
• Kleeneov operator ${𝑳}_1^{*}$ se sastoji od svih nizova znakova koji mogu biti zapisani u obliku $w_1{w}_2...w_n$ sa nizovima znakova $w_i$ u ${𝑳}_1$ i $n\ge 0$. Uočite da ovo uključuje prazni niz $ϵ$ pošto je dozvoljen $n=0$.
• Prevrtanje ${𝑳}_1^R$ se sastoji od preokrenutih verzija svih nizova znakova u ${𝑳}_1$.
• Miješanje (engl. shuffle) jezika ${𝑳}_1$ i ${𝑳}_2$ se sastoji od svih nizova znakova koji mogu biti zapisani u obliku $v_1{w}_1{v}_2{w}_2\dots v_n{w}_n$ gdje je $n\ge 1$ i $v_1,\dots ,v_n$ su nizovi znakova takvi da nadovezivanje $v_1\dots v_n$ je u jeziku ${𝑳}_1$ i $w_1,\dots ,w_n$ su nizovi znakova takvi da je $w_1\dots w_n$ u jeziku ${𝑳}_2$.

Povezano

• Jezik
• Sintaksa
• Semantika
• Prirodni jezik
• Programski jezik

Reference

• Šablon:Cite book
• Šablon:Cite book, poglavlje 6 Algebra of formalized languages.
• Šablon:Cite book
• Šablon:Cite book