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 endre

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   (for sentence, setning). La oss som eit døme ta grammatikken med terminalsymbola  , ikkjeterminalar  , produksjonsreglar

     
    ε (der ε er den tomme strengen)
     
     
     
     
     

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

Her kjem ein enklare grammatikk, som definerer eit liknande språk: Terminalane  , ikkjeterminalane  , startsymbol  , produksjonsreglar

     
    ε

Sjå formell grammatikk for nærare forklaring.

Hierarkiet endre

Chomskyhierarkiet inneheld desse nivåa:

  • Type-1-grammatikkar (kontekst-sensitive grammatikkar) genererer kontekst-sensitive språk. Desse grammatikkane har reglar av forma   med   ein ikkjeterminal og  ,   og   strengar av terminalar og ikkjeterminalar. Strengane   og   kan vere tomme, men   kan ikkje vere tom. Regelen   er tillate viss   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   med   ein ikkjeterminal og   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   er også her tillaten viss   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  
Type-2 Kontekst-fri Ikkjedeterministisk pushdownautomat  
Type-3 Regulære Endeleg tilstandsautomat   og

 

Kjelder endre

Litteratur endre

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