Chomskyhierarkiet
Frå Wikipedia – det frie oppslagsverket
Chomsky-hierarkiet (i visse samanhengar også referert til som Chomsky–Schützenberger hierarchy) er innafor formell lingvistikk og automatteori eit hierarki av klassar av formelle grammatikkar som genererer formelle språk.
Hierarkiet av desse grammatikkana (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.
Innhaldsliste |
[endre] Formelle grammatikkar
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 danne 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
ABS - S ε (der ε er den tomme strengen)
- BA AB
- BS b
- Bb bb
- Ab ab
- Aa aa
og startsymbol S. Denne grammatikken definerer språket til alle orda på forma anbn (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 pSq
- S ε
Sjå formell grammatikk for nærare forklaring.
[endre] Hierarkiet
Chomskyhierarkiet inneheld desse nivåa:
- Type-0-grammatikkar (uavgrensa grammars) inkluderer alle formelle grammatikkar. Dei genererer alle og berre dei språka som kan bli akseptert av ein Turingmaskin. Desse språka er også kjend som rekursift nummererbare språks. Merk at dei er ulik rekursive språk, which kan be bestemt av ein alltid-stoppande Turingmaskin.
- Type-1-grammatikkar (kontekst-sensitive grammatikkar) genererer kontekst-sensitive språk. Desse grammatikkane har reglar av forma
med A ein ikkjeterminal og α, β og γ strengar av terminalar og ikkjeterminalar. Strengane α og β kan vere tomme, men γ kan ikkje vere tom. Regelen 
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-2-grammatikkar (kontekst-frie grammatikkar) genererer kontekst-frie språk. Desse er definrt av reglar av forma
med A ein ikkjeterminal og γ strengar av terminalar og ikkjeterminalar. Desse språka er alle og berre dei språka som kan kjent 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 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 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 | |
| Type-2 | Kontekst-fri | Ikkjedeterministisk pushdownautomat | |
| Type-3 | Regulære | Endeleg tilstandsautomat |  og
|
[endre] Litteratur
- Mal:Cite journal
- Mal:Cite journal
- 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.
[endre] Ekstern lenkje
[endre] Kjelde =
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. | |||
