Formalna gramatika: razlika između inačica

Generativna gramatika se sastoji od skupa pravila za transformiranje nizova znakova koje zovemo ''produkcije''. Prilikom generiranja niza znakova u jeziku započinjemo sas nizom znakova koji se sastoji od samo jednog ''početnog znaka'', i potom uzastopno primjenjujemo pravila (bilo koji broj puta, u bilo kojem redoslijedu) u svrhu prepisivanja (engl. ''rewrite'') niza znakova. Jezik se sastoji od svih nizova znakova koji mogu biti generirani na ovaj način.

Bilo koji pojedinačni slijed valjanih izbora pravila odabranih za vrijeme procesa prepisivanja daje neki pojedinačni niz znakova jezika, i ukolikoako postoji više načina za generiranje jednog niza znakova, tada za gramatiku kažemo da je [[nejednoznačna gramatika|nejednoznačna]].

tada započinjemo sas početnim nezavršnim znakom <math>S</math> te odabiremo produkciju koju nad njim primjenjujemo. Ako odaberemo prvu produkciju, zamjenjujemo <math>S</math> sa <math>aSb</math> te dobivamo međuniz <math>aSb</math>. Ako opet odaberemo prvu produkciju, zamjenjujemo <math>S</math> sa <math>aSb</math> te na taj način generiramo međuniz <math>aaSbb</math>. Ovaj proces ponavljamo sve dok međuniz ne bude sadržavao samo znakove iz abecede (tj. <math>a</math> i <math>b</math>). Ako sad odaberemo drugu produkciju, zamjenjujemo <math>S</math> sa <math>ba</math> pri čemu se generira niz znakova <math>aababb</math> i generiranje je završeno. Ovaj slijed odabira produkcija možemo konciznije zapisati koristeći simbole: <math>S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aababb</math>. Jezik ove gramatike je skup svih nizova znakova koji mogu biti generirani koristeći sljedeći proces: <math>\left \{ba, abab, aababb, aaababbb, ...\right \}</math>.

Klasičnu formalizaciju generativnih gramatika je prvi predložio [[Noam Chomsky]] 1950ih,<ref name="Chomsky1956">Chomsky, Noam, "Three Models for the Description of Language," ''IRE Transactions on Information Theory'', Vol. 2 No. 2, pp. 113-123, 1956.</ref><ref name="Chomsky1957">Chomsky, Noam, ''Syntactic Structures'', Mouton, The Hague, 1957.</ref>, gramatiku ''G'' čine sljedeće komponente:

Kada je [[Noam Chomsky]] prvi iznio formalizam generativnih gramatika 1956.,<ref name="Chomsky1956"/>, klasificirao ih je u tipove danas poznate kao dio [[Chomskyjeva hijerarhija|Chomskyjeve hijerarhije]]. Razlika između ovih tipova jest što imaju povećavajuće stroga produkcijska pravila i stoga mogu izraziti sve manje formalnih jezika. Dva važna tipa su [[kontekstno neovisna gramatika|kontekstno neovisne gramatike]] (tip 2) i [[regularna gramatika|regularne gramatike]] (tip 3). Jezici koji se mogu opisati ovakvim gramatikama se respektivno zovu [[kontekstno neovisni jezik|kontekstno neovisni jezici]] i [[regularni jezik|regularni jezici]]. Premda nešto manje moćne od gramatike neograničenih produkcija (tip 0), koje mogu izraziti bilo koji jezik koji prihvaća [[Turingov stroj]], ova dva ograničena tipa gramatika su najčešće korištena jer se [[parsiranje|parser]] za njih može učinkovito implementirati.<ref name="Grune&Jacobs1990">Grune, Dick & Jacobs, Ceriel H., ''Parsing Techniques—A Practical Guide'', Ellis Horwood, England, 1990.</ref> Na primjer, sve regularne jezike može prepoznati [[konačni automat]], a za korisne podskupove kontekstno neovisnih gramatika postoje dobro poznati algoritmi za generiranje učinkovitih [[LL parser]]a i [[LR parser]]a koji prepoznaju odgovarajuće jezike koje gramatike generiraju.

* ''Tree-adjoining'' gramatike povećavaju ekspresivnost konvencionalnih generativnih gramatika dozvoljavanjem pravilima prepisivanja da operiraju na [[stablo parsiranja|stablima parsiranja]] mjesto na običnim nizovima znakova. <ref name="JoshiEtAl1975">Joshi, Aravind K., ''et al.'', "Tree Adjunct Grammars," ''Journal of Computer Systems Science'', Vol. 10 No. 1, pp. 136-163, 1975.</ref>

* ''The Language Machine'' <ref name="TheLanguageMachine">http://languagemachine.sourceforge.net</ref> izravno implementira neograničene analitičke gramatike (analitičke gramatike neograničenih produkcija). Supstitucijska pravila se koriste za transformiranje ulaza i generiranje izlaza i ponašanja. Sustav također može generirati [http://languagemachine.sourceforge.net/picturebook.html lm-dijagram] koji pokazuje što se događa prilikom primjene pravila analitičke gramatike neograničenih produkcija.

{{izvori|30em}}