Redigerer Chomskyhierarkiet (avsnitt)

== Hierarkiet ==
Chomskyhierarkiet består av disse nivåa:

*'''Type-0-grammatikker''' ([[uavgrensede grammatikker]]) inkluderer alle formelle grammatikker. De genererer alle og bare de språka som kan bli akseptert av en [[turingmaskin]]. Desse språka er også kjent som [[rekursivt nummererbare språk]].

*'''Type-1-grammatikker''' ([[kontekstsensitive grammatikker]]) genererer [[kontekstsensitive språk]]. Disse grammatikkene har regler på forma <math>\alpha A\beta \rightarrow \alpha\gamma\beta</math> med <math>A</math> en ikke-terminal og <math>\alpha</math>, <math>\beta</math> og <math>\gamma</math> strenger av terminaler og ikke-terminaler. Strengene <math>\alpha</math> og <math>\beta</math> kan være tomme, men <math>\gamma</math> kan ikke være tom. Regelen <math>S \rightarrow \epsilon</math> er tillatt viss <math>S</math> ikke opptrer på høyresida av noen regel. Språka som blir beskrevet av disse grammatikkene er alle og bare de språka som kan gjenkjennes av en [[lineært bunden automat]] (en ikke-deterministisk turingmaskin som har en teip som ikke er større enn en konstant faktor av lengda av innputt).

*'''Type-2-grammatikker''' ([[Kontekstfri grammatikk|kontekstfrie grammatikker]]) genererer [[Kontekstfritt språk|kontekstfrie språk]]. Disse er definert av regler på forma <math>A \rightarrow \gamma</math> med <math>A</math> en ikke-terminal og <math>\gamma</math> strenger av terminaler og ikke-terminaler. Disse språka omfatter alle og bare de språka som kan gjenkjennes av en ikke-determinert [[pushdownautomat]]. Kontekstfrie språk er det teoretiske grunnlaget for syntaksen til de fleste [[programmeringsspråk]].

*'''Type-3-grammatikker''' ([[regulære grammatikker]]) genererer de [[Regulært språk|regulære språka]]. En slik grammatikk avgrenser reglene sine til en enkelt ikke-terminal på venstre side og ei høyreside som består av ett og bare ett terminalsymbol, som kan ha ett og bare ett ikke-terminalt symbol før seg eller etter seg, men ikke både før og etter seg. Regelen <math>S \rightarrow \epsilon</math> er også her tillatt viss <math>S</math> ikke opptrer på høyresida av noen regel. Disse og bare disse språka er de språka som kan gjenkjennes av en [[endelig tilstandsautomat]]. I tillegg kan settet av formelle språk bli beskrevet av et [[regulært uttrykk]]. Regulære språk blir blant annet brukt til å definere søkemønstre og til å definere den leksikalske strukturen til programmeringsspråk.

Merk at settet av grammatikker som tilsvarer rekursive språk ikke er medlem av dette hierarkiet.

Alle regulære språk er kontekstfrie, alle kontekstfrie språk er kontekstsensitive, alle kontekstsensitive språk er rekursive, og alle rekursive språk er rekursivt nummererbare. Alle disse er underordna hverandre; det vil si at det fins rekursivt nummererbare språk som ikke er rekursive, rekursive språk som ikke er kontekstsensitive, kontekstsensitive språk som ikke er kontekstfrie, og kontekstfrie språk som ikke er regulære.

Tabellen nedafor oppsummerer hver av de fire grammatikktypene i chomskyhierarkiet, klassen av språk den genererer, typen automat som gjenkjenner den, og forma som reglene i grammatikken må ha.

{| border=1 class="wikitable"
|-
! Grammatikk!!Språk!!Automat!!Produksjonsregler
|-
| Type-0||[[Rekursivt nummererbare språk|Rekursivt nummererbar]]||[[Turingmaskin]]||Ingen restriksjoner
|-
| Type-1||[[Kontekstsensitiv grammatikk|Kontekstsensitive]]||Lineært bunden ikke-deterministisk turingmaskin||<math>\alpha A\beta \rightarrow \alpha\gamma\beta</math>
|-
| Type-2||[[Kontekstfritt språk|Kontekstfri]]||Ikke-deterministisk [[pushdownautomat]]||<math>A \rightarrow \gamma</math>
|-
| Type-3||[[Regulært språk|Regulære]]||[[Endelig tilstandsmaskin|Endelig tilstandsautomat]]||<math>A \rightarrow a</math> og <br />
<math>A \rightarrow aB</math> <br />
|}