Chomskyhierarkiet

Frå Wikipedia – det frie oppslagsverket
Gå til: navigering, søk

Chomsky-hierarkiet (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 | endre wikiteksten]

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[endre | endre wikiteksten]

Chomskyhierarkiet inneheld desse nivåa:

  • 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-3-grammatikkar (regulære grammatikkar) genererer dei regulære språka. Ein slik grammatikk avgrensar reglane sine til ein einskild ikkjeterminal on 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å here 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

Litteratur[endre | endre wikiteksten]

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

Bakgrunnsstoff[endre | endre wikiteksten]

Kjelder[endre | endre wikiteksten]

Engelsk og tysk wikipedia

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.