Chomsky-hierarkin är ett grundläggande begrepp inom teoretisk datavetenskap och formella språk. Noam Chomsky formulerade hierarkin på 1950‑talet för att klassificera grammatiktyper efter vilka produktionsregler de tillåter. Hierarkin delas in i fyra nivåer (typ 0–3). Varje högre numrerad nivå omfattar de språk som finns i de lägre nivåerna:

De fyra nivåerna (översikt)

  • Typ 0 — Obundna grammatik (recursively enumerable): Inga restriktioner på produktionsreglerna. Språken motsvaras av de språk som accepteras av en allmän Turingmaskin.
  • Typ 1 — Kontextkänsliga grammatik: Reglerna kan bero på omgivande symboler. Dessa grammatikers språk accepteras av en linear bounded automaton (LBA), en Turingmaskin med begränsat arbetsminne.
  • Typ 2 — Fria/kontextfria grammatik: Varje produktionsregel har en icke-terminal på vänster sida och en sträng av terminaler och/eller icke‑terminaler på höger sida. De motsvarar de språk som kan accepteras av en pushdown-automaton (stakmaskin).
  • Typ 3 — Reguljära grammatik: Strikta formregler (vanligtvis höger- eller vänsterreguljära), motsvarar reguljära språk. Dessa accepteras av ändliga automater och beskrivs ofta med reguljära uttryck.

Formella formkrav och exempel

  • Typ 3 (reguljära) — typiska produktionsformer: A → aB eller A → a (A, B: icke‑terminaler; a: terminal). Exempel på språk: alla strängar av a och b, a*, eller (ab)*.
  • Typ 2 (kontextfria) — regler: A → γ (A är en icke‑terminal, γ är en sträng av terminaler och/eller icke‑terminaler). Exempel: språket med balanserade parenteser { a^n b^n | n ≥ 0 } kan genereras av en kontextfri grammatik.
  • Typ 1 (kontextkänsliga) — regler där längden på höger sida inte är mindre än vänster sida (utom eventuell regel för tom sträng under särskilda villkor). Exempel: språket { a^n b^n c^n | n ≥ 1 } är kontextkänsligt men ej kontextfritt.
  • Typ 0 (obundna) — inga restriktioner på reglerna (utom att vänster sida innehåller minst en icke‑terminal). Exempel: språk som beskriver egenskaper hos Turingmaskiner (t.ex. kodningar av maskiner som halter) kan vara rekursivt uppräkningsbara men icke‑beslutsbara.

Automater och relationer

  • Typ 3 ↔ ändliga automater (DFA/NFA) och reguljära uttryck.
  • Typ 2 ↔ pushdown-automaton (en eller flera stackar för icke‑deterministiska varianter).
  • Typ 1 ↔ linear bounded automaton (begränsad Turingmaskin).
  • Typ 0 ↔ allmän Turingmaskin.

Egenskaper och användning

  • Inklusionskedja: Reguljära ⊂ Kontextfria ⊂ Kontextkänsliga ⊂ Rekursivt uppräkningsbara (Type‑3 ⊂ Type‑2 ⊂ Type‑1 ⊂ Type‑0).
  • Reguljära språk är stängda under union, konkatenation, Kleene-stjärna, intersection och komplement. Kontextfria språk är stängda under union och konkatenation men inte generellt under intersection och komplement.
  • Beslutsproblem varierar: för reguljära och kontextfria språk finns många effektiva algoritmer (till exempel medlemskapskontroll). För obundna grammatik (typ 0) uppstår odeterministiska och odelbara problem — vissa frågor är ofullständigt beslutsbara eller helt obestämda (undecidable).
  • Praktiska tillämpningar: reguljära språk används i textsökning och lexikal analys, kontextfria grammatik används i programmeringsspråksparsning, och kontextkänsliga modeller kan beskriva mer komplexa språkegenskaper. Typ 0 används främst i teoretisk analys av beräkningsbarhet.

Historisk kontext och notering

Chomsky introducerade hierarkin i arbeten från 1950‑talet. Ursprungligen var syftet att formalisera skillnader mellan olika typer av språk och grammatik, dels för att analysera mänskligt språk, dels för att ge en matematisk grund för studier av beräkningsbarhet och språkigenkänning. I praktisk datavetenskap utgör hierarkin fortfarande en central referensram när man väljer modeller och verktyg för språkbehandling och kompilatorteknik.