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 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.

Grammatikk	Språk	Automat	Produksjonsreglar
Type-0	Rekursivt nummererbar	Turingmaskin	Ingen restriksjonar
Type-1	Kontekst-sensitive	Lineært bunde ikkjedeterministisk turingmaskin	$\alpha A\beta \rightarrow \alpha \gamma \beta$
Type-2	Kontekst-fri	Ikkjedeterministisk pushdownautomat	$A\rightarrow \gamma$
Type-3	Regulære	Endeleg tilstandsautomat	$A\rightarrow a$ og $A\rightarrow aB$

Kjelder

• Denne artikkelen bygger på «Chomsky hierarchy» frå Wikipedia på engelsk, og «Chomsky-Hierarchie» frå Wikipedia på tysk den 17. september 2006.

Litteratur

• Chomsky, Noam (1956). «Three models for the description of language». IRE Transactions on Information Theory (2): 113–124. 
• Chomsky, Noam (1959). «On certain formal properties of grammars». Information and Control (2): 137–167. 
• Noam Chomsky; Marcel P. Schützenberger (1963). «The algebraic theory of context free languages». I Braffort, P.; Hirschberg, D. Computer Programming and Formal Languages. Amsterdam: North Holland. s. 118-161. 

Automatteori: formelle språk og formell grammatikk
Chomsky- hierarkiet	Grammatikkar	Språk	Minimal automat
Type-0	Uavgrensa	Rekursivt nummererbare	Turingmaskin
(ikkje med)	(ikkje noko felles namn)	Rekursive	Decider
Type-1	Kontekst-sensitiv	Kontekst-sensitive	Lineært bunde
Type-2	Kontekst-fri	Kontekst-fri	Pushdown
Type-3	Regulær	Regulær	Finitt
Kvar kategori av språk eller grammatikkar er eit ordentleg subsett av kategorien rett over han.