Grammatiken und die Chomsky-Hierarchie
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.
Beginne mit S. Erlaubt sind und , wobei ε für nichts steht. Kann dabei abab entstehen?
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 . Das leere Wort ε besitzt Länge null. ist die Menge aller endlichen Wörter einschließlich ε. Eine formale Sprache ist eine Teilmenge von .
Für sind etwa ε, a, ab und baa Wörter. Die Schreibweise bedeutet n aufeinanderfolgende a; insbesondere ist . ist dagegen die leere Sprache: Sie enthält kein Wort. Die Sprache enthält genau ein Wort. Ein Zeichen darf in einer Sprache mehrfach vorkommen, obwohl es im Alphabet nur einmal aufgeführt wird.
Grammatik und ihre Regeln
Eine Grammatik ist ein Tupel . V ist die endliche Menge der Nichtterminale oder Variablen, Σ das disjunkte Terminalalphabet, P eine endliche Menge von Regeln und das Startsymbol. Terminale bleiben im fertigen Wort stehen; Nichtterminale bezeichnen noch umzuschreibende Teile.
Eine allgemeine Regel hat die Form . Dabei sind α und β Wörter über , 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.
Ein Schritt und eine vollständige Ableitung
Ein Schritt und eine vollständige Ableitung
Für , und ist aaSbb ein Zwischenstand. Die Regel macht daraus aaaSbbb. Die vorhandenen äußeren Zeichen bleiben an ihrem Platz.
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.
Hier ist . Die Wahl n=0 entsteht durch den direkten Abschluss .
Warum genau diese Sprache entsteht
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.
Nach k Anwendungen der Ausbau-Regel steht . Das gilt zu Beginn für k=0. Ein weiterer Schritt erhöht beide Exponenten um eins.
Rechtslineare Grammatik
Eine rechtslineare Grammatik verwendet nur Regeln , oder , 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. liest a und wechselt nach B. Eine Regel erlaubt, im Zustand A aufzuhören. Für kann man einen zusätzlichen akzeptierenden Endzustand verwenden. Umgekehrt liefert jede Automatenkante eine solche Regel und jeder akzeptierende Zustand eine ε-Regel.
Binärwörter ohne zwei benachbarte Einsen
Binärwörter ohne zwei benachbarte Einsen
Setze und . Verwende und . 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 . 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.
Gehört ein Zwischenstand wie 10S bereits zu L(G)?
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 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 . Als einzige Ausnahme darf 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
- Typ 3 · regulärRechtslineare RegelnEndlicher Automat
Die vorige Sprachklasse ist echt enthalten.
Typ 2 · kontextfreiLinks ein NichtterminalNichtdeterministischer KellerautomatDie vorige Sprachklasse ist echt enthalten.
Typ 1 · kontextsensitivNichtverkürzend, mit ε-AusnahmeLinear beschränkter AutomatDie 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.
Die Form einer gegebenen Grammatik ist keine untere Schranke für ihre Sprache
Die Form einer gegebenen Grammatik ist keine untere Schranke für ihre Sprache
Betrachte , und . Diese Grammatik ist kontextfrei, aber nicht rechtslinear in unserer Normalform. Trotzdem erzeugt sie nur ab. Dieselbe Sprache erhält man rechtslinear durch und . Sie ist also regulär.
Umgekehrt bedeutet ein kontextfreies Erzeugungsverfahren nicht, dass ein endlicher Automat genügen muss. Die Sprache ist kontextfrei, aber nicht regulär. Der Beweis folgt im Pumping-Lemma. Ein weiteres Trennbeispiel ist : 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.
Links- und rechtslineare Regeln beliebig mischen
Links- und rechtslineare Regeln beliebig mischen
Die Regeln und sehen jeweils linear aus: Auf jeder rechten Seite steht höchstens ein Nichtterminal. Daraus wird manchmal auf Regularität geschlossen.
Die Nichtterminale stehen einmal rechts und einmal links. Zusammen erzeugen die Regeln für n≥1: . 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
Welche Aussage unterscheidet ε und richtig?
Wie viele Regelschritte braucht die Grammatik für aaaabbbb?
Wie viele Binärwörter der Länge 3 erzeugt die Grammatik für Wörter ohne 11?
Die Grammatik , , ist nicht rechtslinear. Was folgt für ihre Sprache?
Gib eine rechtslineare Grammatik für alle Binärwörter einschließlich ε an und begründe beide Richtungen.
Welche Sprache erzeugen und ? Warum belegt das ein Problem beim Mischen links- und rechtslinearer Regeln?
Welche der folgenden Regeln verletzt die nichtverkürzende Bedingung von Typ 1, ohne eine erlaubte Startsymbol-Ausnahme zu sein?
Wie kann man bei einer beliebigen Typ-0-Grammatik die Zugehörigkeit eines erzeugbaren Wortes irgendwann bestätigen? Warum ist das noch kein Entscheider?