Redigerer Chomskyhierarkiet

'''Chomskyhierarkiet''' (av og til også referert til som '''Chomsky–Schützenberger-hierarkiet''') er innafor [[informatikk]], formell [[lingvistikk]] og [[automatteori]] et hierarki av klasser av [[Formell grammatikk|formelle grammatikker]] som genererer [[Formelt språk|formelle språk]].

Hierarkiet av disse grammatikkene (også kalt ''frasestrukturgrammatikker'') ble beskrevet av [[Noam Chomsky]] i 1956.  Hierarkiet har også navn etter [[Marcel Schützenberger]] ettersom han spilte ei viktig rolle i utviklinga av teorien om formelle språk.

==Formelle grammatikker==
{{utdypende artikkel|Formell grammatikk}}
En formell grammatikk inneholder et finitt sett av [[terminalsymbol]]er, et finitt sett av [[Ikke-terminalt symbol|ikke-terminale symboler]], et finitt sett av produksjonsregler, med ei venstre- og høyreside som inneholder ord danna av disse symbola, og et ''startsymbol''. En regel blir brukt på et ord ved å erstatte venstresida i regelen med høyresida. En derivasjon er en sekvens av regelapplikasjoner. En slik grammatikk definerer det formelle språket av alle orda som inneholder alle og bare de terminalsymbola som er danna ved derivasjoner ut fra startsymbolet.

Etter en notasjonsmessig konvensjon representeres ikke-terminale symboler med store bokstaver, terminale med små, og startsymbolet med <math>S</math> (for ''sentence'', setning). Som et eksempel kan man ta grammatikken med terminalsymbola <math>\{a, b\}</math>, ikketerminaler <math>\{S, A, B\}</math>, produksjonsregler
: <math>S</math> <math>\rightarrow \,</math> <math>ABS</math>
: <math>S</math> <math>\rightarrow \,</math> ε  (der ε er den tomme strengen)
: <math>BA</math> <math>\rightarrow \,</math> <math>AB</math>
: <math>BS</math> <math>\rightarrow \,</math> <math>b</math>
: <math>Bb</math> <math>\rightarrow \,</math> <math>bb</math>
: <math>Ab</math> <math>\rightarrow \,</math> <math>ab</math>
: <math>Aa</math> <math>\rightarrow \,</math> <math>aa</math>
og startsymbol <math>S</math>. Denne grammatikken definerer språket til alle orda på forma <math> a^n b^n </math> (dvs. <math>n</math> kopier av <math>a</math> og deretter <math>n</math> kopier av <math>b</math>).

Her følger en enklere grammatikk, som definerer et liknende språk: 
Terminalene <math>\{p, q\}</math>, ikke-terminalane <math>\{S\}</math>, startsymbol <math>S</math>, produksjonsregler
: <math>S</math> <math>\rightarrow \,</math> <math>pSq</math>
: <math>S</math> <math>\rightarrow \,</math> ε

== 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 />
|}

==Litteratur==
*{{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
 }}
*{{kilde bok
| forfatter= [[Noam Chomsky]], Marcel P. Schützenberger
| redaktør= Braffort, P.; Hirschberg, D.
| utgivelsesår= 1963
| artikkel=The algebraic theory of context free languages
| tittel= Computer Programming and Formal Languages
| sted=Amsterdam
| forlag=North Holland
| side=118-161
}}
{{Autoritetsdata}}

[[Kategori:Formelle språk]]
[[Kategori:Lingvistikk]]
[[Kategori:Noam Chomsky]]
[[Kategori:Hierarkier]]