Formalni jezik

Izvor: Wikipedija
Skoči na: orijentacija, traži

U matematici, logici i računarstvu, formalni jezik (još i umjetni jezik[1]) Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}} se sastoji od skupa konačnih slijedova elemenata konačnog skupa Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{A}} znakova (simbola). Matematički, to je neuređen par Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\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 Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{A}} se zove abeceda jezika Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}} , a elementi skupa Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{F}} se zovu riječi. U drugom slučaju, skup Obrada nije uspjela. (Conversion error. Server ("https://hr.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\boldsymbol {A}}} se zove leksikon ili vokabular skupa Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{F}} , dok se elementi skupa Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \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. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \left \{ a , b \right \}} , a riječ (string, niz znakova) nad tim alfabetom može biti Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\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. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle a\,} and .

Prazni niz (ili prazna riječ) je riječ duljine 0, i često se označava znakom Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle e\, } , ili Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\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[uredi VE | uredi]

Neki primjeri formalnih jezika:

  • skup svih riječi nad Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle {a, b}\,}
  • skup Obrada nije uspjela. (Conversion error. Server ("https://hr.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \left\{a^{n}\right\}} , gdje je Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle n\,} prirodan broj i znači Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle a\,} ponavljano Obrada nije uspjela. (Conversion error. Server ("https://hr.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n\,} puta
  • Konačni jezici, kao što su Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\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[uredi VE | uredi]

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

Operacije[uredi VE | uredi]

Nekoliko operacija iz teorije skupova može biti korišteno za stvaranje novih jezika iz već postojećih. Pretpostavimo da su Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}_{1}} i Obrada nije uspjela. (Conversion error. Server ("https://hr.wikipedia.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://hr.wikipedia.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. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle vw\,} gdje je Obrada nije uspjela. (Conversion error. Server ("https://hr.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle v\,} niz znakova iz Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}_{1}\,} i Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle w\,} niz znakova iz Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}_{2}\,} .
  • Presjek Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}_1 \cap \boldsymbol{L}_2} jezika i jezika se sastoji od svih nizova znakova koji su sadržani i u Obrada nije uspjela. (Conversion error. Server ("https://hr.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\boldsymbol {L}}_{1}\,} i u Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}_{2}\,} .
  • Unija Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}_1 \cup \boldsymbol{L}_2} jezika Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}_{1}\,} i jezika Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}_{2}\,} se sastoji od svih nizova znakova koji su sadržani ili u Obrada nije uspjela. (Conversion error. Server ("https://hr.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\boldsymbol {L}}_{1}\,} ili u .
  • Komplement Obrada nije uspjela. (Conversion error. Server ("https://hr.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \complement {\boldsymbol {L}}_{1}\,} jezika Obrada nije uspjela. (Conversion error. Server ("https://hr.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\boldsymbol {L}}_{1}\,} se sastoji od svih nizova znakova nad abecedom koji nisu sadržani u Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}_{1}\,} .
  • Desni kvocijent Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}_{1}/\boldsymbol{L}_{2}\,} jezika Obrada nije uspjela. (Conversion error. Server ("https://hr.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\boldsymbol {L}}_{1}\,} jezikom se sastoji od svih nizova znakova Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle v\,} za koje postoji niz znakova Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle w\,} u Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}_{2}\,} takav da je Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle vw\,} u jeziku Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}_{1}} .
  • Kleeneov operator Obrada nije uspjela. (Conversion error. Server ("https://hr.wikipedia.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. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle w_{1}w_{2}...w_{n}\,} sa nizovima znakova Obrada nije uspjela. (Conversion error. Server ("https://hr.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle w_{i}\,} u Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}_{1}\,} i Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle n \ge 0} . Uočite da ovo uključuje prazni niz Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \epsilon\,} pošto je dozvoljen Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle n = 0\,} .
  • Prevrtanje se sastoji od preokrenutih verzija svih nizova znakova u Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}_{1}\,} .
  • Miješanje (engl. shuffle) jezika Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}_{1}\,} i Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}_{2}\,} se sastoji od svih nizova znakova koji mogu biti zapisani u obliku Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle v_{1}w_{1}v_{2}w_{2}\dots v_{n}w_{n}} gdje je Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle n \ge 1} i Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle v_{1},\dots,v_{n}\,} su nizovi znakova takvi da nadovezivanje Obrada nije uspjela. (Conversion error. Server ("https://hr.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle v_{1}\dots v_{n}} je u jeziku Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \boldsymbol{L}_{1}\,} i Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle w_{1},\dots,w_{n}} su nizovi znakova takvi da je Obrada nije uspjela. (Ako je moguće MathML (u pokusnoj fazi): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle w_{1}\dots w_{n}} u jeziku Obrada nije uspjela. (Conversion error. Server ("https://hr.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\boldsymbol {L}}_{2}} .

Također pogledati[uredi VE | uredi]

Izvori[uredi VE | uredi]

  1. Kiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 399
  • 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., 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.
  • Zdravko Dovedan (2003). Formalni jezici - sintaksna analiza, Zavod za informacijske studije FF Zagreb. ISBN 953-175-184-6.
  • Zdravko Dovedan Han (2012). FORMALNI JEZICI I PREVODIOCI - regularni izrazi, gramatike, automati. Element. ISBN 978-953-197-617-6
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.