Chomskyhierarkiet

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

Chomskyhierarkiet (av og til også referert til som Chomsky–Schützenberger-hierarkiet) er innafor informatikk, formell lingvistikk og automatteori et hierarki av klasser av formelle grammatikker som genererer 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[rediger | rediger kilde]

Utdypende artikkel: Formell grammatikk

En formell grammatikk inneholder et finitt sett av terminalsymboler, et finitt sett av 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 S (for sentence, setning). Som et eksempel kan man ta grammatikken med terminalsymbola \{a, b\}, ikketerminaler \{S, A, B\}, produksjonsregler

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 kopier av a og deretter n kopier av b).

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

S \rightarrow \, pSq
S \rightarrow \, ε

Hierarkiet[rediger | rediger kilde]

Chomskyhierarkiet består av disse nivåa:

  • Type-1-grammatikker (kontekstsensitive grammatikker) genererer kontekstsensitive språk. Disse grammatikkene har regler på forma \alpha A\beta \rightarrow \alpha\gamma\beta med A en ikke-terminal og \alpha, \beta og \gamma strenger av terminaler og ikke-terminaler. Strengene \alpha og \beta kan være tomme, men \gamma kan ikke være tom. Regelen S \rightarrow \epsilon er tillatt viss S 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-3-grammatikker (regulære grammatikker) genererer de 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 S \rightarrow \epsilon er også her tillatt viss S 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.

Grammatikk Språk Automat Produksjonsregler
Type-0 Rekursivt nummererbar Turingmaskin Ingen restriksjoner
Type-1 Kontekstsensitive Lineært bunden ikke-deterministisk turingmaskin \alpha A\beta \rightarrow \alpha\gamma\beta
Type-2 Kontekstfri Ikke-deterministisk pushdownautomat A \rightarrow \gamma
Type-3 Regulære Endelig tilstandsautomat A \rightarrow a og

A \rightarrow aB

Litteratur[rediger | rediger kilde]

  • 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: Computer Programming and Formal Languages (red. Braffort, P.; Hirschberg, D.), s. 118-161. North Holland.