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

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   (for sentence, setning). Som et eksempel kan man ta grammatikken med terminalsymbola  , ikketerminaler  , produksjonsregler

     
    ε (der ε er den tomme strengen)
     
     
     
     
     

og startsymbol  . Denne grammatikken definerer språket til alle orda på forma   (dvs.   kopier av   og deretter   kopier av  ).

Her følger en enklere grammatikk, som definerer et liknende språk: Terminalene  , ikke-terminalane  , startsymbol  , produksjonsregler

     
    ε

Hierarkiet rediger

Chomskyhierarkiet består av disse nivåa:

  • Type-1-grammatikker (kontekstsensitive grammatikker) genererer kontekstsensitive språk. Disse grammatikkene har regler på forma   med   en ikke-terminal og  ,   og   strenger av terminaler og ikke-terminaler. Strengene   og   kan være tomme, men   kan ikke være tom. Regelen   er tillatt viss   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 (kontekstfrie grammatikker) genererer kontekstfrie språk. Disse er definert av regler på forma   med   en ikke-terminal og   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æ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   er også her tillatt viss   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  
Type-2 Kontekstfri Ikke-deterministisk pushdownautomat  
Type-3 Regulære Endelig tilstandsautomat   og

 

Litteratur rediger

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