Inačica od 14. srpnja 2021. u 04:55 uredi PonoRoboT (razgovor \| doprinosi) Botovi 208.198 edits m coauthors→last,first ← Starija izmjena		Posljednja izmjena od 2. siječnja 2022. u 18:50 uredi ukloni ovu izmjenu PonoRoboT (razgovor \| doprinosi) Botovi 208.198 edits m RpA: WP:NI, WP:HRV Oznaka: PAWS [2.1]
Redak 36: * Gramatike tipa 1 ([[kontekstno ovisna gramatika\|kontekstno ovisne gramatike]]) generiraju [[kontekstno ovisni jezik\|kontekstno ovisne jezike]]. Ove gramatike imaju produkcije oblika <math>\alpha A\beta \rightarrow \alpha\gamma\beta</math> pri čemu je <math>A</math> nezavršni znak te <math>\alpha</math>, <math>\beta</math> i <math>\gamma</math> nizovi završnih i nezavršnih znakova. Nizovi znakova <math>\alpha</math> i <math>\beta</math> mogu biti prazni, ali niz znakova <math>\gamma</math> mora biti neprazan. Produkcija <math>S \rightarrow \epsilon</math> je dozvoljena ako se <math>S</math> ne pojavljuje na desnoj strani neke produkcije. Jezici koje gramatike ovog tipa opisuju su točno svi jezici koje može prepoznati [[linearno ograničen automat]] (nedeterministički Turingov stroj čija je traka ograničena konstantom puta duljina ulaza.) * Gramatike tipa 2 ([[kontekstno neovisna gramatika\|kontekstno neovisne gramatike]]) generiraju [[kontekstno neovisni jezik\|kontekstno neovisne jezike]]. Imaju produkcije oblika <math>A \rightarrow \gamma</math> pri čemu je <math>A</math> nezavršni znak i <math>\gamma</math> niz završnih i nezavršnih znakova. Ovi jezici su točno svi oni jezici koje može prepoznati nedeterministički [[potisni automat]]. Kontekstno neovisni jezici su teoretska baza za sintaksu većine [[programski jezik\|programskih jezika]]. * Gramatika tipa 3 ([[regularna gramatika\|regularne gramatike]]) generiraju [[regularni jezik\|regularne jezike]]. Takva gramatika ograničava svoje produkcije na jedan nezavršni znak na lijevoj strani produkcije pri čemu se desna strana može sastojati samo od jednog završnog znaka, nakon kojeg slijedi (ili prethodi, ali ne i oboje u istoj gramatici) jedan nezavršni znak. Produkcija <math>S \rightarrow \epsilon</math> je ovdje također dozvoljena ~~ukoliko~~ako se <math>S</math> ne pojavljuje na desnoj strani neke od produkcija. Ovi jezici su točno svi oni jezici koje može odlučiti [[konačni automat]]. Dodatno, ova familija formalnih jezika može biti opisana [[regularni izraz\|regularnim izrazima]]. Regularni jezici se obično koriste za definiranje uzoraka pretrage te analizu leksičke strukture programskog jezika. Uočimo da skup gramatika koji odgovara rekurzivnim jezicima nije prisutan u ovoj hijerarhiji. Redak 73: == Izvori == {{cite journal \|last=Chomsky \|first=Noam \|year=1956 \|title=Three models for the description of language \|journal=IRE Transactions on Information Theory \|issue=2 \|pages=113-124 }} {{cite journal \|last=Chomsky \|first=Noam \|year=1959 \|title=On certain formal properties of grammars \|journal=Information and Control \|issue=2 \|pages=137-167 }} {{cite book \|last1=Chomsky \|first1=Noam \|last2=Schützenberger \|first2=Marcel P. \|editor=Braffort, P.; Hirschberg, D. \|title=Computer Programming and Formal Languages \|year=1963 \|publisher=North Holland \|location=Amsterdam \|pages=118-161 \|chapter=The algebraic theory of context free languages }} {{cite book \|author=Siniša Srbljić \|title=Jezični procesori 1 \|publisher=Element \|year=2003 \|id={{ISBN \|953-197-129-3}}}}

Chomskyjeva hijerarhija: razlika između inačica