Formalni jezik

U matematici, logici i računarstvu, formalni jezik (još i umjetni jezik) Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\boldsymbol {L}}} se sastoji od skupa konačnih slijedova elemenata konačnog skupa ${\boldsymbol {A}}$ znakova (simbola). Matematički, to je neuređen par Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\boldsymbol {L}}} , a elementi skupa Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \left\{a,b\right\}} , a riječ (string, niz znakova) nad tim alfabetom može biti Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle ababba\,} .

Tipični jezik nad abecedom, koji sadrži tu riječ, bi bio skup svih riječi koje sadrže isti broj znakova Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a\,} and Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle b\,} .

Prazni niz (ili prazna riječ) je riječ duljine 0, i često se označava znakom $e\,$, Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \epsilon \,} ili Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {a,b}\,}
• skup Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \left\{a^{n}\right\}} , gdje je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n\,} prirodan broj i $a^{n}\,$ znači Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a\,} ponavljano Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\boldsymbol {L}}_{1}} i Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{2}} jezici nad nekom uobičajenom abecedom.

• Nadovezivanje (ili konkatenacija) Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{1}\boldsymbol{L}_{2}\,} se sastoji od svih nizova znakova oblika Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle vw\,} gdje je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v\,} niz znakova iz Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{1}\,} i Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w\,} niz znakova iz Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{2}\,} .
• Presjek Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_1 \cap \boldsymbol{L}_2} jezika Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{1}\,} i jezika Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{2}\,} se sastoji od svih nizova znakova koji su sadržani i u Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{1}\,} i u Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{2}\,} .
• Unija Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_1 \cup \boldsymbol{L}_2} jezika Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{1}\,} i jezika Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{2}\,} se sastoji od svih nizova znakova koji su sadržani ili u Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{1}\,} ili u Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{2}\,} .
• Komplement Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \complement \boldsymbol{L}_{1}\,} jezika Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{1}\,} se sastoji od svih nizova znakova nad abecedom koji nisu sadržani u Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{1}\,} .
• Desni kvocijent Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{1}/\boldsymbol{L}_{2}\,} jezika Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{1}\,} jezikom Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{2}\,} se sastoji od svih nizova znakova Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v\,} za koje postoji niz znakova Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w\,} u Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{2}\,} takav da je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle vw\,} u jeziku Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{1}} .
• Kleeneov operator Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{1}^{*}} se sastoji od svih nizova znakova koji mogu biti zapisani u obliku Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_{1}w_{2}...w_{n}\,} sa nizovima znakova Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_{i}\,} u Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{1}\,} i Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \ge 0} . Uočite da ovo uključuje prazni niz Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \epsilon\,} pošto je dozvoljen Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 0\,} .
• Prevrtanje Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{1}^{R}\,} se sastoji od preokrenutih verzija svih nizova znakova u Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{1}\,} .
• Miješanje (engl. shuffle) jezika Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{1}\,} i Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{2}\,} se sastoji od svih nizova znakova koji mogu biti zapisani u obliku Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_{1}w_{1}v_{2}w_{2}\dots v_{n}w_{n}} gdje je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \ge 1} i Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_{1},\dots,v_{n}\,} su nizovi znakova takvi da nadovezivanje Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_{1}\dots v_{n}} je u jeziku Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \boldsymbol{L}_{1}\,} i Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_{1},\dots,w_{n}} su nizovi znakova takvi da je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w_{1}\dots w_{n}} u jeziku Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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