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

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
      
    
    {\displaystyle S}
   (for sentence, setning). Som et eksempel kan man ta grammatikken med terminalsymbola 
  
    
      
        {
        a
        ,
        b
        }
      
    
    {\displaystyle \{a,b\}}
  , ikketerminaler 
  
    
      
        {
        S
        ,
        A
        ,
        B
        }
      
    
    {\displaystyle \{S,A,B\}}
  , produksjonsregler

  
    
      
        S
      
    
    {\displaystyle S}
   
  
    
      
        →
        
      
    
    {\displaystyle \rightarrow \,}
   
  
    
      
        A
        B
        S
      
    
    {\displaystyle ABS}
  

  
    
      
        S
      
    
    {\displaystyle S}
   
  
    
      
        →
        
      
    
    {\displaystyle \rightarrow \,}
   ε  (der ε er den tomme strengen)

  
    
      
        B
        A
      
    
    {\displaystyle BA}
   
  
    
      
        →
        
      
    
    {\displaystyle \rightarrow \,}
   
  
    
      
        A
        B
      
    
    {\displaystyle AB}
  

  
    
      
        B
        S
      
    
    {\displaystyle BS}
   
  
    
      
        →
        
      
    
    {\displaystyle \rightarrow \,}
   
  
    
      
        b
      
    
    {\displaystyle b}
  

  
    
      
        B
        b
      
    
    {\displaystyle Bb}
   
  
    
      
        →
        
      
    
    {\displaystyle \rightarrow \,}
   
  
    
      
        b
        b
      
    
    {\displaystyle bb}
  

  
    
      
        A
        b
      
    
    {\displaystyle Ab}
   
  
    
      
        →
        
      
    
    {\displaystyle \rightarrow \,}
   
  
    
      
        a
        b
      
    
    {\displaystyle ab}
  

  
    
      
        A
        a
      
    
    {\displaystyle Aa}
   
  
    
      
        →
        
      
    
    {\displaystyle \rightarrow \,}
   
  
    
      
        a
        a
      
    
    {\displaystyle aa}
  og startsymbol 
  
    
      
        S
      
    
    {\displaystyle S}
  . Denne grammatikken definerer språket til alle orda på forma 
  
    
      
        
          a
          
            n
          
        
        
          b
          
            n
          
        
      
    
    {\displaystyle a^{n}b^{n}}
   (dvs. 
  
    
      
        n
      
    
    {\displaystyle n}
   kopier av 
  
    
      
        a
      
    
    {\displaystyle a}
   og deretter 
  
    
      
        n
      
    
    {\displaystyle n}
   kopier av 
  
    
      
        b
      
    
    {\displaystyle b}
  ).
Her følger en enklere grammatikk, som definerer et liknende språk: 
Terminalene 
  
    
      
        {
        p
        ,
        q
        }
      
    
    {\displaystyle \{p,q\}}
  , ikke-terminalane 
  
    
      
        {
        S
        }
      
    
    {\displaystyle \{S\}}
  , startsymbol 
  
    
      
        S
      
    
    {\displaystyle S}
  , produksjonsregler

  
    
      
        S
      
    
    {\displaystyle S}
   
  
    
      
        →
        
      
    
    {\displaystyle \rightarrow \,}
   
  
    
      
        p
        S
        q
      
    
    {\displaystyle pSq}
  

  
    
      
        S
      
    
    {\displaystyle S}
   
  
    
      
        →
        
      
    
    {\displaystyle \rightarrow \,}
   ε


== 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 
  
    
      
        α
        A
        β
        →
        α
        γ
        β
      
    
    {\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }
   med 
  
    
      
        A
      
    
    {\displaystyle A}
   en ikke-terminal og 
  
    
      
        α
      
    
    {\displaystyle \alpha }
  , 
  
    
      
        β
      
    
    {\displaystyle \beta }
   og 
  
    
      
        γ
      
    
    {\displaystyle \gamma }
   strenger av terminaler og ikke-terminaler. Strengene 
  
    
      
        α
      
    
    {\displaystyle \alpha }
   og 
  
    
      
        β
      
    
    {\displaystyle \beta }
   kan være tomme, men 
  
    
      
        γ
      
    
    {\displaystyle \gamma }
   kan ikke være tom. Regelen 
  
    
      
        S
        →
        ϵ
      
    
    {\displaystyle S\rightarrow \epsilon }
   er tillatt viss 
  
    
      
        S
      
    
    {\displaystyle 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-2-grammatikker (kontekstfrie grammatikker) genererer kontekstfrie språk. Disse er definert av regler på forma 
  
    
      
        A
        →
        γ
      
    
    {\displaystyle A\rightarrow \gamma }
   med 
  
    
      
        A
      
    
    {\displaystyle A}
   en ikke-terminal og 
  
    
      
        γ
      
    
    {\displaystyle \gamma }
   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 
  
    
      
        S
        →
        ϵ
      
    
    {\displaystyle S\rightarrow \epsilon }
   er også her tillatt viss 
  
    
      
        S
      
    
    {\displaystyle 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.


== 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. CS1-vedlikehold: Flere navn: redaktørliste (link)