Chomskyhierarkiet

**Chomskyhierarkiet** (i visse samanhengar også referert til som **Chomsky–Schützenberger-hierarkiet**) er innanfor formell lingvistikk og automatteori eit hierarki av klassar av formelle grammatikkar som genererer formelle språk.

Hierarkiet av desse grammatikkane (også kalla *frasestrukturgrammatikkar*) vart skildra av Noam Chomsky i&nbsp;1956. Hierarkiet har også namn etter Marcel Schützenberger, som spelte ei viktig rolle i utviklinga av teorien om formelle språk.

## Formelle grammatikkar
Ein formell grammatikk inneheld eit finitt sett av terminalsymbol, eit finitt sett av ikkjeterminale symbol, eit finitt sett av produksjonsreglar, med ei venstre- og høgreside som inneheld ord danna av desse symbola, og eit *startsymbol*. Ein regel blir brukt på eit ord med å erstatte venstresida i regelen med høgresida. Ein derivasjon er ein sekvens av regelapplikasjonar. Ein slk grammatikk definerer det formelle språket av alle orda som inneheld alle og berre dei terminale symbola som det er danna med derivasjonar ut i frå startsymbolet.

Etter ein notasjonsmessig konvensjon representerer vi ikkjeterminale symbol med store bokstavar, terminale med små, og startsymbolet med S (for *sentence*, setning). La oss som eit døme ta grammatikken med terminalsymbola \{a, b\}, ikkjeterminalar \{S, A, B\}, produksjonsreglar
: S \rightarrow \, ABS
: S \rightarrow \, ε (der ε er den tomme strengen)
: BA \rightarrow \, AB
: BS \rightarrow \, b
: Bb \rightarrow \, bb
: Ab \rightarrow \, ab
: Aa \rightarrow \, aa
og startsymbol S. Denne grammatikken definerer språket til alle orda på forma  a^n b^n  (dvs. n kopiar av a og deretter n kopiar av b).

Her kjem ein enklare grammatikk, som definerer eit liknande språk: 
Terminalane \{p, q\}, ikkjeterminalane \{S\}, startsymbol S, produksjonsreglar
: S \rightarrow \, pSq
: S \rightarrow \, ε

Sjå formell grammatikk for nærare forklaring.

## Hierarkiet
Chomskyhierarkiet inneheld desse nivåa:

* Type-0-grammatikkar (uavgrensa grammatikkar) inkluderer alle formelle grammatikkar. Dei genererer alle og berre dei språka som kan bli akseptert av ein turingmaskin. Desse språka er også kjend som rekursivt nummererbare språk. Merk at dei er ulik rekursive språk, som kan be *bestemt* av ein alltid-stoppande turingmaskin.

* Type-1-grammatikkar (kontekst-sensitive grammatikkar) genererer kontekst-sensitive språk. Desse grammatikkane har reglar av forma \alpha A\beta \rightarrow \alpha\gamma\beta med A ein ikkjeterminal og \alpha, \beta og \gamma strengar av terminalar og ikkjeterminalar. Strengane \alpha og \beta kan vere tomme, men \gamma kan ikkje vere tom. Regelen S \rightarrow \epsilon er tillate viss S ikkje opptrer på høgresida av nokon regel. Språka som blir skildra av desse grammatikkane er alle og berre dei språka som kan kjend att av ein lineært bunde automat (ein ikkjedeterministisk turingmaskin som har ein tape som ikkje er større enn ein konstant faktor av lenga av input).

* Type-2-grammatikkar (kontekst-frie grammatikkar) genererer kontekst-frie språk. Desse er definert av reglar av forma A \rightarrow \gamma med A ein ikkjeterminal og \gamma strengar av terminalar og ikkjeterminalar. Desse språka er alle og berre dei språka som kan kjenne att av ein ikkje-deterministic pushdownautomat. Kontekstfrie språk er den teoretiske basisen for syntaksen til dei fleste programmeringsspråk.

* Type-3-grammatikkar (regulære grammatikkar) genererer dei regulære språka. Ein slik grammatikk avgrensar reglane sine til ein einskild ikkjeterminal på venstre side og ei høgreside som består av eitt og berre eitt terminalsymbol, som kan ha eitt og berre eitt ikkjeterminalt symbol før seg eller etter seg, men ikkje både før og etter seg. Regelen S \rightarrow \epsilon er også her tillaten viss S ikkje opptrer på høgresida av nokon regel. Desse og berre desse språka er dei språka som kan bli kjent att av ein endeleg tilstandsautomat. I tillegg kan settet av formelle språk bli skildra av eit regulært uttrykk. Regulære språk blir brukt til å definere søkemønster, og til å definere den leksikalske strukturen til programmeringsspråk.

Merk at settet av grammatikkar som svarer til rekursive språk ikkje er ein medlem av dette hierarkiet.

Kvart regulære språk er kontekstfritt, kvart kontekstfrie språk er kontekstsensitivt, og kvart kontekstsensitive språk er rekursivt, og kvart rekursivt språk er rekursivt nummererbart. Alle desse er ordentlege undersett av kvarandre, dvs. at det finst rekursivt nummererbare språk som ikkje er rekursive, rekursive språk som ikkje er kontekstsensitive, og kontekstsensitive språk som ikkje er kontekstfrie, og kontekstfrie språk som ikkje er regulære.

Tabellen nedanfor summerer opp kvar av dei fire grammatikktypane i chomskyhierarkiet, klassen av språk han genererer, typen av automat som godtar han, og forma som reglane i grammatikken må ha.

## Kjelder


**Denne artikkelen bygger på «[[:en:Chomsky hierarchy|Chomsky hierarchy]]» frå , og «[[:de:Chomsky-Hierarchie|Chomsky-Hierarchie]]» frå  den 17. september 2006.*  
 
## Litteratur
* 
* 
*