Formalni jezik

U matematici, logici i računarstvu, formalni jezik (još i umjetni jezik) ${\boldsymbol {L}}$ se sastoji od skupa konačnih slijedova elemenata konačnog skupa ${\boldsymbol {A}}$ znakova (simbola). Matematički, to je neuređen par ${\boldsymbol {L}}=\{{\boldsymbol {A}},{\boldsymbol {F}}\}.$ 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 ${\boldsymbol {A}}$ se zove abeceda jezika ${\boldsymbol {L}}$, a elementi skupa ${\boldsymbol {F}}$ se zovu riječi. U drugom slučaju, skup ${\boldsymbol {A}}$ se zove leksikon ili vokabular skupa ${\boldsymbol {F}}$, dok se elementi skupa ${\boldsymbol {F}}$ 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 $\left\{a,b\right\}$, 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\,$, $\epsilon \,$ ili $\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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a^{n}\,} znači $a\,$ ponavljano $n\,$ puta
• Konačni jezici, kao što su Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \{\{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 ${\boldsymbol {L}}_{1}$ i Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\boldsymbol {L}}_{2}} jezici nad nekom uobičajenom abecedom.

• Nadovezivanje (ili konkatenacija) Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\boldsymbol {L}}_{1}{\boldsymbol {L}}_{2}\,} se sastoji od svih nizova znakova oblika Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle vw\,} gdje je $v\,$ niz znakova iz ${\boldsymbol {L}}_{1}\,$ i Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle w\,} niz znakova iz ${\boldsymbol {L}}_{2}\,$.
• Presjek Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\boldsymbol {L}}_{1}\cap {\boldsymbol {L}}_{2}} jezika ${\boldsymbol {L}}_{1}\,$ i jezika ${\boldsymbol {L}}_{2}\,$ se sastoji od svih nizova znakova koji su sadržani i u ${\boldsymbol {L}}_{1}\,$ i u ${\boldsymbol {L}}_{2}\,$.
• Unija Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\boldsymbol {L}}_{1}\cup {\boldsymbol {L}}_{2}} jezika ${\boldsymbol {L}}_{1}\,$ i jezika ${\boldsymbol {L}}_{2}\,$ se sastoji od svih nizova znakova koji su sadržani ili u ${\boldsymbol {L}}_{1}\,$ ili u ${\boldsymbol {L}}_{2}\,$.
• Komplement Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \complement {\boldsymbol {L}}_{1}\,} jezika ${\boldsymbol {L}}_{1}\,$ se sastoji od svih nizova znakova nad abecedom koji nisu sadržani u ${\boldsymbol {L}}_{1}\,$.
• Desni kvocijent ${\boldsymbol {L}}_{1}/{\boldsymbol {L}}_{2}\,$ jezika ${\boldsymbol {L}}_{1}\,$ jezikom ${\boldsymbol {L}}_{2}\,$ se sastoji od svih nizova znakova $v\,$ za koje postoji niz znakova $w\,$ u ${\boldsymbol {L}}_{2}\,$ takav da je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle vw\,} u jeziku ${\boldsymbol {L}}_{1}$.
• Kleeneov operator Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\boldsymbol {L}}_{1}^{*}} se sastoji od svih nizova znakova koji mogu biti zapisani u obliku Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle w_{1}w_{2}...w_{n}\,} sa nizovima znakova Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle w_{i}\,} u ${\boldsymbol {L}}_{1}\,$ i Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n\geq 0} . Uočite da ovo uključuje prazni niz $\epsilon \,$ pošto je dozvoljen $n=0\,$.
• Prevrtanje Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\boldsymbol {L}}_{1}^{R}\,} se sastoji od preokrenutih verzija svih nizova znakova u ${\boldsymbol {L}}_{1}\,$.
• Miješanje (engl. shuffle) jezika ${\boldsymbol {L}}_{1}\,$ i ${\boldsymbol {L}}_{2}\,$ se sastoji od svih nizova znakova koji mogu biti zapisani u obliku Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle v_{1}w_{1}v_{2}w_{2}\dots v_{n}w_{n}} gdje je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n\geq 1} i $v_{1},\dots ,v_{n}\,$ su nizovi znakova takvi da nadovezivanje Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle v_{1}\dots v_{n}} je u jeziku ${\boldsymbol {L}}_{1}\,$ i Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle w_{1},\dots ,w_{n}} su nizovi znakova takvi da je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle w_{1}\dots w_{n}} u jeziku Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\boldsymbol {L}}_{2}} .

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

Izvori

• Nepoznat parametar: id

Helena Rasiowa and Roman Sikorski (1970) The Mathematics of Metamathematics., poglavlje 6 Algebra of formalized languages.

• Nepoznat parametar: id

• Nepoznat parametar: id

• Nepoznat parametar: id

• Zdravko Dovedan Han (2012). FORMALNI JEZICI I PREVODIOCI - regularni izrazi, gramatike, automati. Element. ISBN 978-953-197-617-6