I teoretisk informatikk , språkteori og beregningsevne er Chomsky-hierarkiet (noen ganger kalt Chomsky- Schützenberger- hierarkiet ) en klassifisering av formelle grammatikker (og i forlengelse av de respektive formelle språk generert av grammatikker), beskrevet av Noam Chomsky i 1956 .
Hierarkiet introdusert av Noam Chomsky er basert på den formelle grammatikkmodellen . Han definerer klassene i hierarkiet som mulige modeller for beskrivelsen av naturlige språkers strukturelle egenskaper. Noam Chomsky foreslo en klassifisering i fire typer språk, fra type 0 til type 3. Denne første terminologien har blitt opprettholdt, men andre navn er nå mer vanlig. Chomsky presenterte disse familiene i form av formelle grammatikker, og de forskjellige klassene grammatikkene er definert av suksessive begrensninger i form av reglene.
En bemerkelsesverdig egenskap ved Chomsky-klassifiseringen er at det for hver type er en familie av automater som aksepterer nøyaktig språk av den typen. Disse kontrollerne varierer i arten og bruken av hjelpeminnet. Oversettelsen til kompleksitetsklasser er mindre tydelig: rasjonelle språk (type 3) er i DTIME (n), algebraiske språk (type 2) i DTIME (n 3 ), kontekstuelle språk (type 1) i DTIME ( n M ), hvor M avhenger av grammatikken, men det omvendte er ikke sant.
Chomskys klassifisering, tatt opp i nesten alle informatikkhåndbøker for datavitenskap, har vist seg å være svært fruktbar i sine applikasjoner, spesielt når det gjelder design og analyse av programmeringsspråk og utarbeidelse av disse språkene. Rasjonelle og algebraiske språk har tidligere vært gjenstand for omfattende teoretiske studier. De kontekstsensitive språkene brukes hovedsakelig i beskrivelsen av naturlige språk.
Chomsky definerte fire klasser av grammatikk, kalt type 0 til type 3, og derfor også fire klasser av språk, generert av disse hierarkisk nestede grammatikkene:
Alle språk for type 3 er språk for type 2. Alle språk for type 2 er språk for språk 1. Alle språk for type 1 er språk for type 0. Følgende tabell oppsummerer samsvaret mellom grammatikktyper, språk og maskiner.
Grammatikk | Produksjonsregler | Språk | Maskin |
---|---|---|---|
skriv inn 0 | rekursivt opptellingen | Turing maskin | |
type 1 | kontekstuell | Lineær avgrenset automat | |
type 2 | algebraisk | Ikke-deterministisk stakeautomat | |
type 3 | rasjonell | Ferdig automat |
I den formelle presentasjonen nedenfor, er vokabularet til grammatikk, sammensatt av terminale og ikke-terminale symboler , er settet med ikke-terminale symboler, og er det tomme ordet.
Det er ingen begrensninger på reglene. De har formen:
Disse grammatikkene genererer klassen med rekursivt tallrike språk . Dette er nøyaktig språkene som kan gjenkjennes av en Turing-maskin . Problemet med om et ord tilhører et språk i denne klassen er ubestemmelig .
Reglene er av form:
Med andre ord inkluderer enhver regel en ikke-terminal omgitt av to ord som beskriver konteksten variabelen kan erstattes i. Disse grammatikkene kalles kontekstuelle (på engelsk kontekst-sensitive ), fordi erstatningen av et ikke-terminal element kan avhenge av elementene rundt det: dets kontekst. Språkene som produseres, kalt kontekstuelle eller kontekstsensitive språk , er nøyaktig de som gjenkjennes av en ikke-deterministisk Turing-maskin med lineært avgrenset minne, ofte kalt lineært avgrenset automat . Andre tilsvarende formuleringer finnes for grammatikk som definerer kontekstuelle språk.
Reglene er av form:
En slik regel kan sees på som en kontekstuell regel der konteksten til reglene er tom, forutsatt at riktig medlem ikke er det tomme ordet. Adjektivet "ikke-kontekstuelt" uttrykker det faktum at ikke-terminale symboler behandles uavhengig av hvor de vises. Disse grammatikkene genererer nøyaktig algebraiske språk , også kalt kontekstfrie språk, akontekstuelle språk eller ikke-kontekstuelle språk. De gjenkjennes av en batteridrevet automat .
Vanlige grammatikker er enten venstre lineære grammatikk eller høyre lineære grammatikk:
Vanlige grammatikker genererer rasjonelle språk . Faktisk blir en vanlig grammatikk lett forvandlet til en endelig automat ( Kleenes teorem ).
Oppmerksomhet, vi kan ikke autorisere de to typene regler samtidig i en grammatikk uten å forlate klassen av rasjonelle språk: vi får de lineære grammatikkene som utgjør en mellomklasse mellom type 2 og type 3. Reglene for en grammatisk lineær er av skjema:
Se også eksemplene på den formelle grammatikksiden . Teorien om formelle språk har mange verktøy for å bekrefte eller ugyldiggjøre språktypen (rasjonell, algebraisk, etc.). Den eksplisitte konstruksjonen av en grammatikk som gjenkjenner et gitt språk er ikke alltid lett.
Chomskys opprinnelige hierarki besto av fire klasser. Andre klasser blir ofte ispedd:
De tre tilstøtende grammatikker definere en familie mellom algebraiske språk og kontekstsensitive språk. De aksepteres av batteridrevne automater ombord . Disse grammatikkene er en del av grammatikkene som gir bedre forståelse av strukturen til naturlige språk, gruppert under navnet litt kontekstsensitivt språk (en) .
Det finnes andre forbedringer som viser at strukturen ikke er "lineær": hvis vi for eksempel sammenligner lineære språk og deterministiske algebraiske språk, ser vi at disse familiene ikke er inneholdt i den ene.
Chomsky-hierarkiet gjelder bare domenet til det kalkulerbare som defineres paradigmatisk av hva en Turing-maskin kan beregne . Utover det eksisterer andre språkhierarkier, inkludert det aritmetiske hierarkiet .