Lektion 2.1

Grammatiken und die Chomsky-Hierarchie

45 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • Alphabet, Wort, Sprache, Terminal und Nichtterminal unterscheiden,

  • eine Grammatik als Tupel angeben und einzelne Ableitungsschritte begründen,

  • reguläre und kontextfreie Regeln an Beispielen vergleichen,

  • die vier Sprachklassen mit ihren Maschinenmodellen verbinden und die Grenzen der Einordnung benennen.

Vorausgesetzt: Deterministische endliche Automaten (DEA), Nichtdeterministische Automaten und die Potenzmengenkonstruktion

Ein Automat liest ein fertiges Wort und entscheidet, ob er es annimmt. Man kann dieselbe Frage von der anderen Seite angehen: Welche Regeln erzeugen genau die erlaubten Wörter? Ein Compiler braucht etwa Regeln für Ausdrücke und verschachtelte Klammern. Eine Liste aller erlaubten Texte wäre unendlich; eine endliche Regelmenge kann trotzdem genügen.

Beginnen wir mit einem Bauverfahren: Schreibe S, ersetze S entweder durch aSb oder durch nichts. Jeder weitere Ausbau legt ein a links und ein b rechts um den noch offenen Teil. Die Regeln beschreiben damit eine Beziehung zwischen beliebig weit voneinander entfernten Zeichen. Wir untersuchen zuerst solche Ableitungen und dann, wie die erlaubte Form einer Regel die Ausdruckskraft begrenzt.

Vermute zuerst

Beginne mit S. Erlaubt sind S→aSbS\to aSb und S→εS\to\varepsilon, wobei ε für nichts steht. Kann dabei abab entstehen?

Definition

Alphabet, Wort und formale Sprache

Ein Alphabet Σ ist eine endliche Menge von Zeichen. Ein Wort über Σ ist eine endliche Folge dieser Zeichen. Seine Länge heißt ∣w∣|w|. Das leere Wort ε besitzt Länge null. Σ∗\Sigma^* ist die Menge aller endlichen Wörter einschließlich ε. Eine formale Sprache ist eine Teilmenge von Σ∗\Sigma^*.

Für Σ={a,b}\Sigma=\{a,b\} sind etwa ε, a, ab und baa Wörter. Die Schreibweise ana^n bedeutet n aufeinanderfolgende a; insbesondere ist a0=εa^0=\varepsilon. ∅\varnothing ist dagegen die leere Sprache: Sie enthält kein Wort. Die Sprache {ε}\{\varepsilon\} enthält genau ein Wort. Ein Zeichen darf in einer Sprache mehrfach vorkommen, obwohl es im Alphabet nur einmal aufgeführt wird.

Definition

Grammatik und ihre Regeln

Eine Grammatik ist ein Tupel G=(V,Σ,P,S)G=(V,\Sigma,P,S). V ist die endliche Menge der Nichtterminale oder Variablen, Σ das disjunkte Terminalalphabet, P eine endliche Menge von Regeln und S∈VS\in V das Startsymbol. Terminale bleiben im fertigen Wort stehen; Nichtterminale bezeichnen noch umzuschreibende Teile.

Eine allgemeine Regel hat die Form α→β\alpha\to\beta. Dabei sind α und β Wörter über V∪ΣV\cup\Sigma, und α enthält mindestens ein Nichtterminal. β darf leer sein. Bei ihrer Anwendung ersetzt man ein zusammenhängendes Vorkommen der vollständigen linken Seite durch die vollständige rechte Seite. Der Rest bleibt unverändert. Das Zeichen | zwischen rechten Seiten bedeutet eine Auswahl zwischen mehreren Regeln.

xαy⇒Gxβyfalls (α→β)∈Px\alpha y\Rightarrow_G x\beta y\quad\text{falls }(\alpha\to\beta)\in P
Beispiel

Ein Schritt und eine vollständige Ableitung

Für V={S}V=\{S\}, Σ={a,b}\Sigma=\{a,b\} und P={S→aSb, S→ε}P=\{S\to aSb,\ S\to\varepsilon\} ist aaSbb ein Zwischenstand. Die Regel S→aSbS\to aSb macht daraus aaaSbbb. Die vorhandenen äußeren Zeichen bleiben an ihrem Platz.

⇒G∗\Rightarrow_G^* bezeichnet null oder mehr Schritte. Die von G erzeugte Sprache besteht nur aus fertigen Terminalwörtern. Ein Zwischenstand mit S gehört deshalb noch nicht zu dieser Sprache.

L(G)={w∈Σ∗∣S⇒G∗w},S⇒aSb⇒aaSbb⇒aabbL(G)=\{w\in\Sigma^*\mid S\Rightarrow_G^*w\},\qquad S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb

Hier ist L(G)={anbn∣n≥0}L(G)=\{a^nb^n\mid n\ge0\}. Die Wahl n=0 entsteht durch den direkten Abschluss S→εS\to\varepsilon.

Schritt für Schritt

Warum genau diese Sprache entsteht

Eine Sprache richtig anzugeben verlangt zwei Richtungen: Jedes erzeugte Wort muss die behauptete Form haben, und jedes Wort dieser Form muss erzeugbar sein.

  1. Nach k Anwendungen der Ausbau-Regel steht akSbka^kSb^k. Das gilt zu Beginn für k=0. Ein weiterer Schritt erhöht beide Exponenten um eins.

Schritt 1 von 3
Definition

Rechtslineare Grammatik

Eine rechtslineare Grammatik verwendet nur Regeln A→aBA\to aB, A→aA\to a oder A→εA\to\varepsilon, wobei A,B Nichtterminale und a ein Terminal sind. Das verbleibende Nichtterminal steht also rechts. Diese Normalform genügt für alle regulären Sprachen, also die von endlichen Automaten erkannten Sprachen.

Eine Ableitung lässt sich als Automatenlauf lesen: Das aktuelle Nichtterminal ist der Zustand. A→aBA\to aB liest a und wechselt nach B. Eine Regel A→εA\to\varepsilon erlaubt, im Zustand A aufzuhören. Für A→aA\to a kann man einen zusätzlichen akzeptierenden Endzustand verwenden. Umgekehrt liefert jede Automatenkante eine solche Regel und jeder akzeptierende Zustand eine ε-Regel.

Beispiel

Binärwörter ohne zwei benachbarte Einsen

Setze V={S,A}V=\{S,A\} und Σ={0,1}\Sigma=\{0,1\}. Verwende S→0S∣1A∣εS\to0S\mid1A\mid\varepsilon und A→0S∣εA\to0S\mid\varepsilon. S bedeutet: Eine Eins wäre jetzt erlaubt. A bedeutet: Das zuletzt erzeugte Zeichen war eine Eins; als nächstes Zeichen ist nur null erlaubt. Beide Zustände dürfen die Ableitung beenden.

Zum Beispiel gilt S⇒1A⇒10S⇒101A⇒1010S⇒10101A⇒10101S\Rightarrow1A\Rightarrow10S\Rightarrow101A\Rightarrow1010S\Rightarrow10101A\Rightarrow10101. Ein 11 kann nicht entstehen, weil A keine Regel mit einer führenden Eins hat. Jedes Binärwort ohne 11 lässt sich wiederum Zeichen für Zeichen nach diesen Regeln aufbauen.

Kurz geprüft

Gehört ein Zwischenstand wie 10S bereits zu L(G)?

Definition

Vier Stufen der Chomsky-Hierarchie

Die Chomsky-Hierarchie ordnet Sprachklassen nach möglichen Grammatikformen. Typ 3 ist rechtslinear. Bei Typ 2, den kontextfreien Grammatiken, steht links genau ein Nichtterminal; rechts darf ein beliebiges Wort stehen. Damit ist etwa S→aSbS\to aSb erlaubt.

Für Typ 1, die kontextsensitiven Sprachen, verwenden wir die gleichmächtige Beschreibung durch nichtverkürzende Regeln: Die linke Seite enthält ein Nichtterminal und ∣α∣≤∣β∣|\alpha|\le|\beta|. Als einzige Ausnahme darf S→εS\to\varepsilon vorkommen, wenn S auf keiner rechten Seite steht. Diese Ausnahme ermöglicht auch das leere Wort. Bei Typ 0 gibt es außer den allgemeinen Grammatikbedingungen keine Einschränkung der Regeln. Typ-0-Sprachen heißen auch rekursiv aufzählbar: Eine Turingmaschine kann ihre Wörter erkennen, muss bei Nichtmitgliedern aber nicht halten.

Die vier zugehörigen Maschinenmodelle stehen in der folgenden Übersicht. Ein Kellerautomat hat einen Stapel als Speicher. Ein linear beschränkter Automat ist eine nichtdeterministische Turingmaschine mit einer durch die Eingabelänge linear begrenzten Zahl von Bandfeldern. Diese stärkeren Modelle werden in den folgenden Kapiteln genauer behandelt.

Mehr erlaubte Regeln, mehr beschreibbare Sprachen

  1. Typ 3 · regulärRechtslineare RegelnEndlicher Automat
  2. Die vorige Sprachklasse ist echt enthalten.

    Typ 2 · kontextfreiLinks ein NichtterminalNichtdeterministischer Kellerautomat
  3. Die vorige Sprachklasse ist echt enthalten.

    Typ 1 · kontextsensitivNichtverkürzend, mit ε-AusnahmeLinear beschränkter Automat
  4. Die vorige Sprachklasse ist echt enthalten.

    Typ 0 · rekursiv aufzählbarAllgemeine GrammatikregelnTuringmaschine als Erkenner

Die Einordnung betrifft die Sprache: Sie gehört zu einer Klasse, wenn es mindestens eine passende Grammatik gibt. Die Übersicht verwendet für Typ 1 die beschriebene Ausnahme für das leere Wort. Keller- und Turingmaschinen werden später im Kurs ausgearbeitet.

Beispiel

Die Form einer gegebenen Grammatik ist keine untere Schranke für ihre Sprache

Betrachte S→ABS\to AB, A→aA\to a und B→bB\to b. Diese Grammatik ist kontextfrei, aber nicht rechtslinear in unserer Normalform. Trotzdem erzeugt sie nur ab. Dieselbe Sprache erhält man rechtslinear durch S→aBS\to aB und B→bB\to b. Sie ist also regulär.

Umgekehrt bedeutet ein kontextfreies Erzeugungsverfahren nicht, dass ein endlicher Automat genügen muss. Die Sprache {anbn∣n≥0}\{a^nb^n\mid n\ge0\} ist kontextfrei, aber nicht regulär. Der Beweis folgt im Pumping-Lemma. Ein weiteres Trennbeispiel ist {anbncn∣n≥1}\{a^nb^nc^n\mid n\ge1\}: kontextsensitiv, aber nicht kontextfrei; der spätere Abschnitt zu kontextfreien Grammatiken begründet die zweite Aussage. Für die letzte Trennung genügt das später behandelte Halteproblem: Es ist rekursiv aufzählbar und unentscheidbar, während kontextsensitive Sprachen entscheidbar sind. Diese Trennungen sind Sätze, keine bloßen Folgen der Schreibweise einzelner Regeln.

Häufige Fehler

Links- und rechtslineare Regeln beliebig mischen

Die Regeln S→aAS\to aA und A→Sb∣bA\to Sb\mid b sehen jeweils linear aus: Auf jeder rechten Seite steht höchstens ein Nichtterminal. Daraus wird manchmal auf Regularität geschlossen.

Richtig ist

Die Nichtterminale stehen einmal rechts und einmal links. Zusammen erzeugen die Regeln anbna^nb^n für n≥1: S⇒aA⇒aSb⇒aaAb⇒aabbS\Rightarrow aA\Rightarrow aSb\Rightarrow aaAb\Rightarrow aabb. Rechtslinear und linkslinear liefern jeweils für sich reguläre Sprachen; die beliebige Mischung ist keine reguläre Grammatik. Außerdem klassifiziert man immer alle Regeln der gegebenen Grammatik gemeinsam.

Zusammenfassung

  • Eine Grammatik ist ein endliches Erzeugungsverfahren. Zur Sprache gehören nur vollständig abgeleitete Terminalwörter.

  • Ein Sprachbeweis zeigt beide Richtungen: keine unerwünschten Wörter und jedes gewünschte Wort.

  • Rechtslineare Grammatiken und endliche Automaten beschreiben dieselben regulären Sprachen.

  • Typ 2 erlaubt das kontextfreie Ersetzen eines Nichtterminals; Typ 1 lässt sich nichtverkürzend beschreiben; Typ 0 erlaubt allgemeine Regeln.

  • Mit der benannten ε-Konvention gilt: regulär ist echt in kontextfrei, echt in kontextsensitiv, echt in rekursiv aufzählbar enthalten.

  • Eine umständliche Grammatik macht ihre Sprache nicht schwerer. Für die Sprachklasse zählt die Existenz einer passenden Darstellung.

Übungen

Aufgabe 1Multiple Choice

Welche Aussage unterscheidet ε und ∅\varnothing richtig?

Aufgabe 2Numerisch

Wie viele Regelschritte braucht die Grammatik S→aSb∣εS\to aSb\mid\varepsilon für aaaabbbb?

Aufgabe 3Numerisch

Wie viele Binärwörter der Länge 3 erzeugt die Grammatik für Wörter ohne 11?

Aufgabe 4Multiple Choice

Die Grammatik S→ABS\to AB, A→aA\to a, B→bB\to b ist nicht rechtslinear. Was folgt für ihre Sprache?

Aufgabe 5Freitext

Gib eine rechtslineare Grammatik für alle Binärwörter einschließlich ε an und begründe beide Richtungen.

Aufgabe 6Freitext

Welche Sprache erzeugen S→aAS\to aA und A→Sb∣bA\to Sb\mid b? Warum belegt das ein Problem beim Mischen links- und rechtslinearer Regeln?

Aufgabe 7Multiple Choice

Welche der folgenden Regeln verletzt die nichtverkürzende Bedingung von Typ 1, ohne eine erlaubte Startsymbol-Ausnahme zu sein?

Aufgabe 8Freitext

Wie kann man bei einer beliebigen Typ-0-Grammatik die Zugehörigkeit eines erzeugbaren Wortes irgendwann bestätigen? Warum ist das noch kein Entscheider?