Chomskyjeva hijerarhija – razlika između verzija

Uklonjeni sadržaj Dodani sadržaj
Addbot (razgovor | doprinos)
m Bot: migracija 32 međuwiki veza sada dostupnih na stranici d:q190913 na Wikidati
m Bot: popravljanje preusmjeravanja
Red 33:
produkcija]]) uključuju sve formalne gramatike. Generiraju točno sve jezike koje može prepoznati [[Turingov stroj]]. Ovi su jezici još i poznati kao [[rekurzivno prebrojiv jezik|rekurzivno prebrojivi jezici]]. Uočimo razliku između njih i [[rekurzivni jezik|rekurzivnih jezika]] koje ''odlučuje'' [[Stroj koji uvijek staje|Turingov stroj koji uvijek staje]].
* 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 neovisnanezavisna gramatika|kontekstno neovisne gramatike]]) generiraju [[kontekstno neovisninezavisni 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 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.
 
Red 60:
|-
| Tip 2
| [[kontekstnoKontekstno neovisnanezavisna gramatika|Kontekstno neovisna]]
| Nedeterministički [[potisni automat]]
| <math>A \rightarrow \gamma</math>