Chomsky Hierarchy

Sprachen (Deutsch, Java, HTML) haben Regeln (Grammatik). Noam Chomsky sortierte alle Grammatiken in 4 Schubladen (Typ 0 bis 3). Je kleiner die Zahl, desto mächtiger (und schwieriger zu verarbeiten).

Typ 3 (Regulär): Einfach. (Suchen/Ersetzen). Automat: Endlicher Automat (DFA).
Typ 2 (Kontextfrei): Verschachtelt. (Klammern (( ))). Automat: Kellerautomat (PDA).
Typ 1 (Kontextsensitiv): Komplex. (Natürliche Sprache teilweise).
Typ 0 (Rekursiv aufzählbar): Alles. (Turing-Maschine). Das ist die Landkarte der Informatik.

Merksatz: Eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen nach ihrer generativen Mächtigkeit ordnet (Typ 0 bis Typ 3).

RegEx: Typ 3. Gut für Email-Validierung. Schlecht für HTML-Parsing (weil HTML verschachtelt ist -> Typ 2).
Compiler (Parser): Typ 2. Programmiersprachen sind meist "Kontextfrei". Man nutzt Backus-Naur-Form (BNF) und Parser-Generatoren (Yacc/Bison).
XML/HTML: Typ 2. Man braucht einen Stack (Keller), um Tags zu matchen (<div>...</div>).

1. Pumping Lemma

Das Tool, um zu beweisen, wo eine Sprache steht. "Kann ein Automat unendlich zählen?" Ein Endlicher Automat (Typ 3) kann nicht zählen ("a^n b^n" -> n mal a, dann n mal b). Er vergisst n. Ein Kellerautomat (Typ 2) kann zählen (pusht 'a' auf den Stack, popt bei 'b'). Er kann aber nicht "a^n b^n c^n" zählen (dafür bräuchte er zwei Stacks -> Turing Maschine).

2. Linearly Bounded Automaton (LBA)

Für Typ 1. Eine Turing-Maschine, die nur so viel Band hat wie der Input lang ist. Fast so mächtig wie Turing, aber entscheidbar (Halteproblem lösbar für LBA, aber extrem teuer).

1. Komplexität & Entscheidbarkeit

Die Hierarchie ist eng mit der Komplexitätstheorie verknüpft:

Typ 3: $O(n)$ Zeit, extrem wenig Speicher.
Typ 2: $O(n^3)$ Zeit (CYK-Algorithmus). Man kann jede kontextfreie Sprache in kubischer Zeit parsen.
Typ 1: PSPACE-complete. Das Parsen kann exponentiell viel Zeit kosten.
Typ 0: Unentscheidbar. Du kannst keinen Algorithmus schreiben, der für jede Typ-0 Grammatik sicher sagt: "Ja, dieses Wort gehört dazu", ohne in Endlosschleifen zu geraten. Für Software-Entwickler bedeutet das: Nutze immer die schwächstmögliche Grammatik! Wer RegEx (Typ 3) nutzen kann, sollte keinen Parser-Generator (Typ 2) bauen.

2. Mildly Context-Sensitive Languages

In der Computerlinguistik hat man gemerkt, dass Typ 2 zu schwach für menschliche Sprache (z. B. Schweizerdeutsch oder Niederländisch) ist, Typ 1 aber viel zu komplex zu verarbeiten. Man erfand eine Zwischenschicht: Mildly Context-Sensitive Languages. Dazu gehören Tree-Adjoining Grammars (TAGs). Sie erlauben es, "Cross-Serial Dependencies" abzubilden (A hängt von C ab, B von D), bleiben aber in polynomialer Zeit ($O(n^6)$ oder besser) parssbar. Das ist der Stand der Technik für formale Modelle natürlicher Sprache.

3. Church-Turing-These & Typ 0

Grammatiken vom Typ 0 sind exakt äquivalent zu Turingmaschinen. Das bedeutet: Alles, was wir als "Algorithmus" oder "berechenbar" bezeichnen, lässt sich als eine Menge von Ersetzungsregeln (Produktionen) darstellen. Dies führt zu faszinierenden Erkenntnissen: Man kann mit simplen "String-Ersetzungen" (wie in der Sprache Thue) einen vollwertigen Computer simulieren. Für die Sicherheit ist das eine Warnung: Wenn eine Config-Datei oder ein Makro-System mächtig genug ist, um Typ-0 Regeln abzubilden, ist es "Turing-complete" und damit potenziell ein Einfallstor für Malware, die man nicht automatisiert auf Bösartigkeit prüfen kann.