Qualifikationsphase

Q3.1 · Formale Sprachen und Grammatiken

Von Mehrdeutigkeit zu eindeutigen Zeichenfolgen, Regeln und Ableitungen

Natürliche Sprache ist für Menschen oft gerade deshalb effizient, weil Situation, Vorwissen und gemeinsame Erwartungen nicht jedes Mal ausgesprochen werden müssen. Für eine Maschine reicht dieser offene Kontext nicht aus: Sie braucht explizite Festlegungen darüber, welche Zeichenfolgen zulässig sind.

Q3.1 entwickelt diese Festlegungen am Beispiel einer Robotersprache: von einzelnen Zeichen über Wörter bis zu einer formalen Sprache. Q3.2 knüpft daran an und prüft mit endlichen Automaten, ob ein Wort zu einer regulären Sprache gehört.

Kerncurriculum kompakt
Grammatiken, Ableitungen und Sprachklassen in Q3.1

Q3.1 ist gemeinsam mit Q3.2 verbindlicher Bestandteil von Q3.

Im grundlegenden Niveau geht es um das Erzeugen und Beschreiben formaler Sprachen: Grammatiken werden gelesen, Wörter abgeleitet und die erzeugte Sprache bestimmt.

Der Leistungskurs ergänzt die systematische Einordnung in die Chomsky-Hierarchie.

Grundlegendes Niveau

Reguläre und kontextfreie Grammatiken fachsprachlich beschreiben und unterscheiden.
Wörter durch schrittweise Anwendung von Produktionen ableiten.
Ableitungen als Ableitungsbaum darstellen und vorgegebene Ableitungsbäume prüfen.
Syntaxdiagramme als alternative Darstellung formaler Regeln lesen und verwenden.
Die von einer Grammatik erzeugte Sprache bestimmen und die Zugehörigkeit konkreter Wörter begründen.

Erhöhtes NiveauLK

Grammatiken und formale Sprachen in die Chomsky-Hierarchie einordnen.
Die Sprachklassen anhand ihrer Regelbeschränkungen und Ausdrucksmächtigkeit unterscheiden.
Die Hierarchie als Zusammenhang von Grammatikklassen, Sprachklassen und passenden Automatenmodellen erläutern, ohne unbeauftragte Beweisvertiefungen.

Sprache als Zeichensystem
Von Zeichen über Alphabet und Wort zu einer klar abgegrenzten Sprache

Warum braucht die Informatik formale Sprachen?

Natürliche Sprachen sind für die Kommunikation zwischen Menschen entwickelt und verwendet. Menschen können Äußerungen auch dann verstehen, wenn sie mehrdeutig sind, Informationen auslassen, vom sprachlichen oder situativen Kontext abhängen oder kleinere Abweichungen von sprachlichen Konventionen enthalten.

Interpretationsspielraum entsteht dabei auf mehreren Ebenen: Derselbe Ausdruck kann Verschiedenes bedeuten, Bezüge innerhalb eines Satzes können unterschiedlich verstanden werden, und eine Äußerung kann unausgesprochene Voraussetzungen mitführen. Menschen bewältigen das häufig durch Kontext, Weltwissen und gemeinsame Erwartungen. Diese Offenheit ist kein Mangel, sondern eine Stärke menschlicher Kommunikation.

Weil nicht jede Voraussetzung ausdrücklich formuliert werden muss, kann natürliche Sprache flexibel, knapp und dennoch verständlich sein. Für die regelgeleitete Verarbeitung durch ein Computersystem entsteht daraus jedoch eine andere Anforderung: Das System muss ohne Rückgriff auf Alltagserfahrung oder offenen Kontext reproduzierbar prüfen können,

welche Zeichen verwendet werden dürfen,
welche Zeichenfolgen zulässig sind,
nach welchen Regeln sie gebildet werden und
wie ihre Zulässigkeit systematisch geprüft wird.

Natürliche und formale Sprache lösen unterschiedliche Aufgaben

Natürliche Sprache

Sie ist für Menschen eine flexible, kontextreiche Form der Kommunikation. Gerade weil nicht jede Voraussetzung ausgeschrieben werden muss, lassen sich Bedeutungen oft schnell und verdichtet vermitteln. Mehrdeutigkeit wird dabei durch Interpretation aufgelöst.

Formale Sprache

Sie legt Zeichenvorrat und zulässige Zeichenfolgen ausdrücklich fest. Dadurch wird der für die jeweilige Aufgabe notwendige Interpretationsspielraum reduziert: Systeme können Eingaben reproduzierbar prüfen, parsen, übertragen oder ausführen.

Formale Sprache ist deshalb nicht allgemein besser oder schneller. Ihre Stärke liegt in präziser, automatisierbarer Verarbeitung in festgelegten Systemen; dafür bezahlt sie mit weniger Ausdrucksmöglichkeiten und mit expliziten Regeln. Auch eine formal korrekte Zeichenfolge erhält ihre Bedeutung nicht automatisch: Syntax und Semantik werden im nächsten Abschnitt bewusst getrennt.

Vom Sprachproblem zum Robotermodell

Für einen Roboter muss genau festgelegt werden, welche Zeichen verwendet werden dürfen und welche daraus gebildeten Zeichenfolgen als Befehle gelten. Das System soll nicht aus Alltagserfahrung oder offenem Kontext erschließen, ob eine Eingabe vermutlich gemeint war. Deshalb werden zunächst das Alphabet und die möglichen Wörter bestimmt. Anschließend wird festgelegt, welche dieser Wörter tatsächlich zur Robotersprache gehören.

Alphabet, Wort und Sprache

Ein Alphabet benennt die erlaubten einzelnen Zeichen. Daraus entstehen Wörter; eine Sprache wählt aus diesen Wörtern die aus, die zusätzlich einem festgelegten Muster entsprechen.

Alphabet und Wortmenge lesenΣ · Σ* · ε · ∈ · ∉ · ⊆

Eine Menge und ein Alphabet aufschreiben

Σ_Roboter = {F, L, R, 0, 1, ;}

Name: Menge und Alphabet; Σ ist das große griechische Sigma.
So liest man: „Sigma Roboter ist die Menge F, L, R, null, eins und Semikolon.“
Das bedeutet: Das Roboteralphabet enthält genau diese einzelnen erlaubten Zeichen. Geschweifte Klammern fassen Elemente zusammen, das Komma trennt sie und = benennt die Zusammenstellung.
Beispiel: F und ; sind je ein Zeichen dieses Alphabets.
Nicht verwechseln: Σ ist hier kein Summenzeichen. Der tiefgestellte Zusatz Roboter gehört zum Namen, nicht zum Roboterwort.

Zeichenfolgen zuordnen

F1; ∈ L_Roboter

Name: Zugehörigkeitszeichen ∈; sein Gegenzeichen ist ∉.
So liest man: „F eins Semikolon ist Element von L Roboter.“ Mit ∉: „… ist nicht Element von …“
Das bedeutet: Ein einzelnes Wort kann Element einer Menge sein; hier gehört F1; zur ausgewählten Sprache.
Beispiel: X1; ∉ Σ_Roboter*, weil X im Alphabet fehlt.
Nicht verwechseln: Eine ganze Sprache kann Teilmenge einer anderen Menge sein; ein einzelnes Wort nicht.

Alle Wörter über einem Alphabet

Σ_Roboter*

Name: Stern-Operator für die Wortmenge über einem Alphabet.
So liest man: „Sigma Roboter Stern“ oder: „alle endlichen Wörter über dem Roboteralphabet“.
Das bedeutet: Jede endliche Aneinanderreihung erlaubter Zeichen gehört dazu – auch noch unvollständige Befehle.
Beispiel: F; ∈ Σ_Roboter*, obwohl es kein vollständiger Befehl ist.
Nicht verwechseln: Der Stern ist keine Multiplikation. Aneinanderschreiben wie F1; bedeutet Verkettung.

Das leere Wort

ε ∈ Σ* aber ε ∉ L_Roboter

Name: Epsilon, der kleine griechische Buchstabe für das leere Wort.
So liest man: „Epsilon gehört zu Sigma Stern, aber nicht zu L Roboter.“
Das bedeutet: Das leere Wort hat kein Zeichen und ist trotzdem ein Wort über jedem Alphabet. Die Robotersprache verlangt mindestens einen Befehl.
Beispiel: |ε| = 0: Die Länge des leeren Wortes ist null.
Nicht verwechseln: ε ist kein sichtbares Alphabetzeichen und nicht die leere Menge.

Sprache als Auswahl

L_Roboter ⊆ Σ_Roboter*

Name: Teilmenge; ⊆ bedeutet „ist Teilmenge von“.
So liest man: „L Roboter ist Teilmenge von Sigma Roboter Stern.“
Das bedeutet: Jedes Wort der Robotersprache benutzt nur erlaubte Zeichen und erfüllt zusätzlich das Befehlsmuster.
Beispiel: F; ∈ Σ_Roboter* \ L_Roboter: Das Zeichenmaterial ist erlaubt, aber die Ziffer fehlt.
Nicht verwechseln: Der Schrägstrich \ bedeutet Mengendifferenz: „aus Sigma Stern ohne die Wörter aus L“, nicht „geteilt durch“.

Ein Zeichen ist ein einzelnes Symbol, etwa F oder ;. Das Alphabet legt fest, welche Zeichen überhaupt vorkommen dürfen.
Ein Wort ist eine endliche Zeichenfolge aus diesem Alphabet. Erst danach wird geprüft, ob die Folge auch das zusätzliche Befehlsmuster erfüllt.
Die formale Sprache wählt aus allen erlaubten Zeichenfolgen genau die vollständigen Roboterbefehle und Befehlsfolgen aus.

In L_Roboter besteht jeder Befehl aus Befehlssymbol, Binärziffer und Semikolon. Die oben entschlüsselte Kurzform fasst beliebig viele solcher vollständigen Befehle zusammen.

Schaubild der begrifflichen Ebenen: Zeichen bilden ein endliches Alphabet. Daraus entstehen Wörter in Sigma Stern; die formale Robotersprache L wählt zulässige Wörter als Teilmenge aus. — Das Schaubild ordnet begriffliche Ebenen und Mengenbeziehungen. Es zeigt keinen Vorgang, in dem ein einzelnes Wort in eine Sprache umgewandelt wird.

Wie die Mengen zusammenhängen

Das Alphabet Σ_Roboter ist endlich. Seine Zeichen können aber zu Wörtern beliebiger endlicher Länge zusammengesetzt werden. Weil das Alphabet nicht leer ist, enthält Σ* unendlich viele Wörter; auch das leere Wort ε gehört dazu.

Nicht jede dieser Zeichenfolgen ist ein Roboterbefehl. L_Roboter ist eine Teilmenge von Σ_Roboter*: Sie enthält nur Wörter, die das zusätzliche Bildungs- beziehungsweise Zulässigkeitskriterium erfüllen. Eine Sprache ist damit keine weitere einzelne Zeichenfolge, sondern eine Menge von Wörtern.

Ausblick auf Q3.2: Für diese reguläre Robotersprache kann ein endlicher Automat später ein konkretes Wort Zeichen für Zeichen lesen und akzeptieren oder verwerfen. Welche Automatentypen zu welchen Sprachklassen passen, wird dort erst systematisch untersucht.

Drei verschiedene Urteile

Prüfe eine Zeichenfolge immer in dieser Reihenfolge. So bleibt sichtbar, ob ein Fehler schon am Alphabet liegt oder erst am Sprachmuster.

Enthält die Zeichenfolge ausschließlich Zeichen des Alphabets?
Falls ja: Ist sie ein Wort über dem Alphabet, also w ∈ Σ*?
Erfüllt sie zusätzlich das Sprachkriterium und liegt damit in L?

w ∉ Σ*: Mindestens ein Zeichen gehört nicht zum Alphabet.
w ∈ Σ* \ L: Alle Zeichen sind erlaubt, aber das Sprachmuster ist nicht erfüllt.
w ∈ L: Das Wort benutzt nur erlaubte Zeichen und erfüllt das Sprachkriterium.

Sprachzugehörigkeit prüfenw ∉ Σ* · w ∈ Σ* \ L · w ∈ L

Diese drei Urteile sind keine drei Namen für dasselbe Problem: Sie markieren drei verschiedene Stellen der Prüfung.

Ein fremdes Zeichen

w ∉ Σ*

Laut: „w ist nicht Element von Sigma Stern.“

Urteil: Mindestens ein Zeichen gehört nicht zum Alphabet. Beispiel: X1; ∉ Σ_Roboter*.

Erlaubte Zeichen, falsches Muster

w ∈ Σ* \ L

Laut: „w ist in Sigma Stern ohne L.“

Urteil: Alle Zeichen sind erlaubt, aber das zusätzliche Sprachkriterium ist verletzt. Beispiel: F; ∈ Σ_Roboter* \ L_Roboter.

Vollständiger Befehl

w ∈ L

Laut: „w ist Element von L.“

Urteil: Das Wort besteht aus erlaubten Zeichen und erfüllt zusätzlich das Sprachkriterium. Beispiel: F1; ∈ L_Roboter.

Sprachmuster und Wortlängen lesencᵢ · dᵢ · k ≥ 1 · {0,1}+ · |w|

Ein wiederholbares Befehlsmuster

L_Roboter = {c₁d₁; … c_kd_k; | k ≥ 1, c_i ∈ {F, L, R}, d_i ∈ {0, 1}}

Name: Indizes, Auslassungspunkte und die Bedingung k ≥ 1.
So liest man: „L Roboter ist die Menge c eins d eins Semikolon bis c k d k Semikolon, für die k mindestens eins ist …“
Das bedeutet: Ein Wort hat einen ersten, zweiten und bis zu einem k-ten Befehl. Jedes c_i ist F, L oder R; jedes d_i ist 0 oder 1.
Beispiel: Bei F1;R0; sind c₁=F, d₁=1, c₂=R, d₂=0 und k=2.
Nicht verwechseln: … beschreibt ein Muster und gehört nicht zum Wort. + in {0,1}+ heißt „mindestens ein Zeichen“, nicht Addition.

Wortlänge und Zeichenzählung

{w ∈ L_ST | |w| = 5}

Name: Variable w und Wortlänge |w|.
So liest man: „Die Menge aller w aus L ST, für die die Länge von w gleich fünf ist.“
Das bedeutet: Die senkrechten Striche direkt um ein Wort bedeuten dessen Zeichenzahl.
Beispiel: |s01e| = 4. Für x = 101 bedeutet |x|₁ = 2: In x kommen zwei Einsen vor.
Nicht verwechseln: Das tiefgestellte 1 zählt hier Einsen; es ist kein weiteres Zeichen des Wortes.

Die Bauform einer beschriebenen Menge

{w ∈ Σ* | zusätzliche Bedingung}

Name: Beschreibende Mengenschreibweise.
So liest man: „Die Menge aller w aus Sigma Stern, für die die zusätzliche Bedingung gilt.“
Das bedeutet: {…} eröffnet die Menge; w ist ein Platzhalter; ∈ nennt die Grundmenge; der mittlere Strich trennt die Bedingung ab.
Beispiel: {w ∈ Σ* | w endet auf ;} beschreibt Wörter, die mit einem Semikolon enden.
Nicht verwechseln: Der mittlere Strich heißt hier „für die gilt“, in Z → 0E | 1E dagegen „oder“ und in |w| „Länge von w“.

Sensortelegramme vollständig übersetzen

L_ST = {sxe | x ∈ {0,1}+ und x enthält genau eine 1}

Name: Sensortelegrammsprache mit variablem Mittelteil x.
So liest man: „L ST ist die Menge s x e, wobei x aus mindestens einem null-oder-eins-Zeichen besteht und genau eine Eins enthält.“
Das bedeutet: Jedes Telegramm beginnt mit s, endet mit e und hat dazwischen einen nichtleeren Binärteil mit genau einer 1.
Beispiel: s01e gehört dazu: x=01 ist nicht leer und enthält genau eine Eins.
Nicht verwechseln: x ist ein Platzhalter für den Mittelteil, nicht der Buchstabe x im Telegramm. Das hochgestellte + ist keine Addition.

Lernspur · Formale Sprachen untersuchen

Prüfe Wörter in mehreren Sprachen, erschließe Sprachkriterien, vergleiche zwei Sprachen über demselben Alphabet und lege abschließend selbst eine formale Sprache fest.

Erste Lernspur starten

Syntax und Semantik: Form und Wirkung trennen
Eine Grammatik beschreibt zunächst die Form, nicht die Situation

Syntax beschreibt, ob eine Zeichenfolge der vereinbarten Form entspricht. Semantik beschreibt ihre Bedeutung oder Wirkung im jeweiligen Modell. Formale Verarbeitung braucht eine eindeutige Struktur, bevor weitere Regeln oder eine Ausführung sinnvoll angewendet werden können.

Das sind zwei getrennte Urteile: Das Syntaxurteil fragt nur nach der formalen Regel. Das Situationsurteil fragt erst danach, ob ein syntaktisch gültiger Befehl in der beschriebenen Lage sinnvoll oder problematisch ist. Eine Grammatik simuliert die Welt nicht.

Syntax: zulässige Form

F1 ist syntaktisch ungültig, weil das Semikolon fehlt. X1; ist ungültig, weil X kein vorgesehenes Befehlssymbol ist.

Semantik: Bedeutung und Situation

F1; kann auf freier Fläche sinnvoll sein. Direkt vor einer Wand ist derselbe syntaktisch gültige Befehl operativ problematisch. Die Grammatik behauptet nicht, Computer hätten keine Bedeutungsebene; sie modelliert nur die zulässige Form.

Merksatz

Syntax ist notwendig, aber nicht hinreichend für eine sinnvolle Wirkung: Erst muss die Form stimmen; dann kann Bedeutung oder Ausführbarkeit beurteilt werden.

Lernspur · Syntax und Wirkung unterscheiden

Triff zu denselben Roboterbefehlen zwei unabhängige Urteile.

Station 2 starten

Formale Grammatik als erzeugendes Modell
G = (N, T, P, S): Rollen eindeutig unterscheiden

Eine formale Grammatik erzeugt Wörter, indem sie ein Startsymbol schrittweise ersetzt. Ihre Bestandteile werden als 4-Tupel notiert. Beim Roboter entsteht das Modell in zwei sichtbaren Schritten: erst genau ein Befehl, danach eine nichtleere Folge von Befehlen.

Grammatiken und Produktionen lesenG = (N, T, P, S) · → · |

Eine Grammatik als geordnetes 4-Tupel

G = (N, T, P, S)

Name: Geordnetes 4-Tupel einer Grammatik.
So liest man: „Gleich G ist das Tupel aus N, T, P und S.“
Das bedeutet: N sind Nicht-Terminale, T Terminale, P Produktionen und S das Startsymbol. Runde Klammern und Kommas halten diese vier Rollen in dieser Reihenfolge zusammen.
Beispiel: Für die Ein-Befehl-Grammatik gilt N={S,Z,E}, T={F,L,R,0,1,;}; P enthält die Regeln und das Startsymbol ist S.
Nicht verwechseln: Die runden Klammern sind weder Mengenklammern noch Multiplikation. Wir schreiben „Startsymbol: S“ statt der missverständlichen Kurzform S=S.

Eine Produktionsregel

Z → 0E | 1E

Name: Produktionskopf Z, Produktionspfeil →, Produktionsrumpf rechts davon.
So liest man: „Z wird zu null E oder eins E.“
Das bedeutet: Wenn in einer Satzform Z vorkommt, darf es durch 0E oder 1E ersetzt werden. Aneinanderschreiben bedeutet: Diese Symbole folgen direkt aufeinander.
Beispiel: S → FZ → F1E → F1; entsteht Schritt für Schritt aus passenden Produktionen.
Nicht verwechseln: Der Alternativstrich | heißt hier „oder“. Ein Pfeil der späteren Ableitung steht dagegen für genau eine konkrete Produktionsanwendung.

Stufe A · genau ein Befehl

G_Befehl = (N, T, P, S)

N = {S, Z, E}
T = {F, L, R, 0, 1, ;}
Startsymbol: S

P = {
S → FZ | LZ | RZ
Z → 0E | 1E
E → ;
}

Stufe A erzeugt genau einen vollständigen Roboterbefehl. Die Leitfrage lautet: Wie muss die Grammatik verändert werden, damit beliebig viele vollständige Befehle aufeinander folgen können?

Stufe B · Befehlsfolge

G_Roboter = (N, T, P, S)

N = {S, A, Z, E}
T = {F, L, R, 0, 1, ;}
Startsymbol: S

P = {
S → FZ | LZ | RZ
A → FZ | LZ | RZ | ε
Z → 0E | 1E
E → ;A
}

N: Nicht-Terminale S, A, Z, E stehen für noch zu erzeugende Struktur: Start, Anschluss, Ziffer und Abschluss. In Stufe A fehlt A noch.
T: Terminale bilden allein das fertige Wort.
S: Das Startsymbol ist der Ausgangspunkt jeder Ableitung.
P: Produktionen sind erlaubte Ersetzungen. In Z → 1E sind Z der Produktionskopf, → der Produktionspfeil und 1E der Produktionsrumpf.

Terminale und Nicht-Terminale sind hier disjunkt: Kein Symbol nimmt gleichzeitig beide Rollen ein. Die Modellierungsentscheidung von Stufe A zu Stufe B ist klein, aber entscheidend: A kommt hinzu, E → ; wird zu E → ;A, und A startet einen weiteren Befehl oder beendet die Folge mit A → ε.

Komponentenmodell einer Grammatik als 4-Tupel mit Nicht-Terminalen, Terminalen, Produktionen und Startsymbol — Das 4-Tupel trennt Hilfssymbole, Ergebniszeichen, erlaubte Schritte und den Startpunkt des Erzeugungsprozesses.

Lernspur · Grammatik Schritt für Schritt

Bestimme zuerst die Bausteine von Stufe A und erweitere sie danach kontrolliert zu Stufe B.

Station 3 starten

Ableitung, Nicht-Ableitbarkeit und L(G)
Vom einzelnen Erzeugungsweg zur allgemeinen Sprachmenge

Eine Ableitung beginnt beim Startsymbol. Ein Pfeil verbindet zwei Satzformen nach genau einer Produktionsanwendung. Derselbe Pfeil ist in einer Produktion wie Z → 1E der Produktionspfeil; in einer Ableitung zeigt er den einzelnen Übergang von einer Satzform zur nächsten.

Ableitungen und erzeugte Sprachen lesenS → FZ → F1E → F1; · L(G)

Eine konkrete Ableitung

S → FZ → F1E → F1;

Name: Ableitungskette aus Satzformen.
So liest man: „Aus S wird FZ, daraus F eins E und daraus F eins Semikolon.“
Das bedeutet: Jeder Pfeil ersetzt genau ein Nicht-Terminal mit einer passenden Produktion. Die Zwischenformen dürfen noch Nicht-Terminale enthalten.
Beispiel: Der Schritt FZ → F1E verwendet die Produktion Z → 1E.
Nicht verwechseln: Eine Produktion ist eine allgemeine erlaubte Regel; eine Ableitung ist ihre konkrete Anwendung auf eine vorhandene Satzform.

Die ganze erzeugte Sprache

L(G_Roboter)

Name: Sprache der Grammatik G Roboter.
So liest man: „L von G Roboter.“
Das bedeutet: Gemeint ist die Menge aller Terminalwörter, die diese Grammatik vom Startsymbol aus erzeugen kann.
Beispiel: F1; ∈ L(G_Roboter), weil die gezeigte Ableitung bei F1; endet.
Nicht verwechseln: Die runden Klammern ordnen die Sprache der Grammatik zu. Sie sind keine Mengen- und keine Rechenklammern.

Stufe A: ein Befehl

S → FZ → F1E → F1;

Die Satzformen zwischen Start und Terminalwort dürfen Nicht-Terminale enthalten. Bei F1; sind nur Terminale übrig.

Stufe B: eine Befehlsfolge

S → FZ → F1E → F1;A → F1;RZ → F1;R0E → F1;R0;A → F1;R0;

A macht die Wahl sichtbar: weiterer Befehl oder Abschluss mit ε. ε verschwindet als leere Symbolfolge aus dem erzeugten Terminalwort.

Satzform und Terminalwort unterscheiden

Eine Satzform ist ein Zwischenergebnis einer Ableitung und darf noch Nicht-Terminale enthalten. Ein Terminalwort ist erst erreicht, wenn nur Terminale übrig sind. S → FZ → F1E → F1 ist keine gültige Ableitung: Auf E ist E → ;A anwendbar. Auch F; ist nicht ableitbar, weil nach F zwingend Z → 0E | 1E folgt.

Die ganze Sprache statt einzelner Beispiele

Eine Ableitung zeigt einen Erzeugungsweg. L(G_Roboter) beschreibt dagegen alle Terminalwörter, für die mindestens eine gültige Ableitung vom Startsymbol existiert. Deshalb gilt etwa F1; ∈ L(G_Roboter), aber F; ∉ L(G_Roboter). Eine erfolglose begrenzte Suche ist für sich allein kein Beweis für w ∉ L(G).

Lernspur · Ableitungen aufbauen

Baue einzelne Produktionsschritte auf und wechsle danach von einem Erzeugungsweg zu L(G).

Station 4 starten

Ableitungsbaum und Syntaxdiagramm lesen
Hierarchie und Wegdarstellung für dieselbe Regellogik

Die lineare Ableitung zeigt die zeitliche Folge der Ersetzungen. Im Ableitungsbaum ist die Wurzel das Startsymbol, innere Knoten sind ersetzte Nicht-Terminale, ihre Kinder bilden den Produktionsrumpf und die Blattfolge von links nach rechts ergibt das Wort.

Ableitungsbaum: Struktur sichtbar machen

Der Baum entsteht aus derselben Stufe-B-Ableitung wie oben: F1;R0;. Die Wurzel ist S; jeder innere Knoten wird durch genau eine Produktion erweitert. Bei A → ε ist ε als Blatt sichtbar, trägt aber kein Zeichen zum Terminalwort bei.

Die kanonische Baumprojektion wird geladen.

Die Blattfolge ohne ε lautet F1;R0;. Eine passende Blattfolge allein genügt nicht: Auch Produktionszuordnung und Kindreihenfolge müssen stimmen.

Syntaxdiagramm: erlaubte Wege

Ein Syntaxdiagramm zeigt mögliche Wege durch eine Regel, nicht die zeitliche Entstehung eines einzelnen Wortes. Terminale sind Ovale; Nicht-Terminale sind Rechtecke und verweisen auf weitere Regeln. Alternativen, ε-Pfade und Rekursion folgen dem selben Fachmodell wie die Grammatik.

Die kanonische Syntaxdiagrammprojektion wird geladen.

Der Repräsentationsunterschied ist wichtig: Der Ableitungsbaum fragt: „Wie wurde dieses konkrete Wort erzeugt?“ Das Syntaxdiagramm fragt: „Welche Wege erlaubt die Regel allgemein?“

Lernspur · Ableitung als Baum darstellen

Überführe die geprüfte Roboterableitung selbst in einen Baum. Danach folgt die Perspektive des Syntaxdiagramms.

Station 6 starten

Reguläre Grammatik: rechts- und linksregulär
Produktionsformen begrenzen die Struktur auf gerichtetes Wachstum

Eine rechtsreguläre Produktion hat sinngemäß die Form A → aB, A → a oder A → ε. Rechts steht also höchstens ein Nicht-Terminal, und wenn es vorkommt, steht es am rechten Ende. G_Roboter erfüllt dies mit Z → 1E, E → ;A und A → ε.

Rechtsregulär: nach rechts weiterbauen

Das noch zu ersetzende Nicht-Terminal wandert ans rechte Ende. Flache Befehlsfolgen wie F0;L1; lassen sich mit endlich vielen Strukturzuständen beschreiben.

Linksregulär: in die Gegenrichtung

Bei einer linksregulären Grammatik steht ein mögliches Nicht-Terminal links vom Terminalteil, etwa A → Ba, A → a oder A → ε. Das Wort wächst entgegengesetzt. Links- und rechtsreguläre Grammatiken erzeugen dieselbe Sprachklasse, werden innerhalb einer Grammatik aber nicht unkontrolliert gemischt.

Modellgrenze im Regeltyp

Reguläre Produktionen erlauben eine lineare Fortsetzung mit endlich vielen unterscheidbaren Situationen. Das reicht für flache Folgen, nicht jedoch für beliebig tief offene und später passend zu schließende Strukturen. „Diese Grammatik ist rechtsregulär“ beschreibt ihre Produktionsform; dass sie eine reguläre Sprache erzeugt, ist eine getrennte, fachlich abgesicherte Sprachklassenaussage.

Lernspur · Reguläre Grammatik einordnen und entwickeln

Ordne zuerst die gesamte bekannte Grammatik ein und entwickle anschließend ein kleines eigenes reguläres Modell.

Station 7 starten

Reguläre Grammatik und Automat übersetzen
Erzeugen und Erkennen als zwei Darstellungen derselben Struktur

Eine rechtsreguläre Grammatik lässt sich konstruktiv in einen endlichen Automaten überführen. Die Standardkonstruktion kann zunächst einen NEA oder eine unvollständige Übergangsstruktur liefern. Q3.1 zeigt die Brücke; die vollständige Automatenanalyse folgt in Q3.2.

Beschriftete Übergänge lesenq_S —F→ q_Z

Ein beschrifteter Zustandsübergang

q_S —F→ q_Z

Name: Zustandsübergang mit gelesenem Zeichen.
So liest man: „Von q S führt beim Lesen von F ein Übergang nach q Z.“
Das bedeutet: Links steht der Ausgangszustand, über dem Pfeil das gelesene Zeichen und rechts der Zielzustand.
Beispiel: Die Produktion S → FZ kann als Übergang q_S —F→ q_Z dargestellt werden.
Nicht verwechseln: Dieser Pfeil beschreibt einen Zustandswechsel; der Produktionspfeil beschreibt eine Regel, der Ableitungspfeil einen konkreten Ersetzungsschritt. Tiefgestellte Zeichen gehören hier zum Zustandsnamen.

Von Grammatik zu einem Automaten

Nicht-Terminale werden zu Zuständen: S, A, Z, E werden zu q_S, q_A, q_Z, q_E.
S → FZ wird q_S —F→ q_Z; Z → 1E wird q_Z —1→ q_E.
E → ;A wird q_E —;→ q_A.
A → ε markiert q_A als Endzustand; q_S ist der Startzustand.
Die konkrete Roboterstruktur kann deterministisch gelesen werden. Erst für einen vollständigen DEA führen alle nicht genannten Eingaben in einen nicht akzeptierenden Fehlerzustand mit Selbstschleifen.

Beim Wort F1;R0; führt der Zustandsweg von q_S über q_Z, q_E und q_A wieder zu q_A und akzeptiert dort.

Von DEA zu Grammatik

Aus Zuständen werden Nicht-Terminale, aus Übergängen Produktionen. So wird q_Z —0→ q_E zu q_Z → 0q_E. Ein Endzustand erhält die Abschlussregel q_A → ε.

Die Benennung kann wechseln; die Regelstruktur bleibt dieselbe. Grammatik erzeugt ein Wort, Automat liest es und erreicht bei einem akzeptierten Wort einen Endzustand.

Lernspur · Grammatik und Automat überführen

Arbeite die Zuordnung im Automatenwerkzeug aus und vergleiche danach die erzeugende und erkennende Sicht.

Station 8 starten

Kontextfreie Grammatik und die Grenze regulärer Modelle
Beliebige Schachtelung braucht mehr als endlich viele Zustände

Die flache Sprache L_Roboter kennt keine offene Struktur, die später passend geschlossen werden muss. Anders ist es bei Wiederholungsblöcken: In W{F1;W{L0;}} muss zu jeder geöffneten Klammer die passende schließende Klammer gehören – bei nicht von vornherein begrenzter Tiefe.

Klammern als Meta- oder Wortzeichen{…} · W{F1;} · T = {…}

Gleiche Zeichen, unterschiedliche Rolle

Name: Mengenklammern in der Metaschreibweise und Terminalzeichen im erzeugten Wort.
So liest man: In T = {W, F, L, R, 0, 1, ;, {, }} sammeln die äußeren Klammern Elemente einer Menge. In W{F1;} werden die inneren Klammern als Zeichen des Wortes gelesen.
Das bedeutet: Die Grammatik benutzt Klammern, um ihre Mengen zu beschreiben, und kann zugleich die Zeichen { und } als Terminale erzeugen.
Beispiel: W{F1;} besteht aus W, einer öffnenden Klammer, F1; und einer schließenden Klammer.
Nicht verwechseln: Die Menge {F,L,R} ist kein Wort. Die Klammern in einem Blockwort sind dagegen kein Kommentar und keine mathematische Gruppierung.

Kontextfreie Blockgrammatik

G_Block = (N, T, P, S); Startsymbol: B

N = {B, C, D}
T = {W, F, L, R, 0, 1, ;, {, }}

P = {
B → CB | W{B}B | C | W{B}
C → FD; | LD; | RD;
D → 0 | 1
}

Bei jeder kontextfreien Produktion steht links genau ein Nicht-Terminal. Rechts darf eine beliebige Folge aus Terminalen und Nicht-Terminalen stehen. Die rekursive Regel B → W{B} erlaubt daher unbeschränkt tiefe Struktur.

Eine regelkonforme verschachtelte Ableitung lautet: B → W{B} → W{CB} → W{FD;B} → W{F1;B} → W{F1;W{B}} → W{F1;W{C}} → W{F1;W{LD;}} → W{F1;W{L0;}}.

Geschachtelte Chomsky-Hierarchie mit regulären und kontextfreien Sprachen — Jede reguläre Sprache ist kontextfrei; die Blocksprache zeigt, dass die Umkehrung nicht gilt.

Flach und regulär

F0;, R1;L0; und F1;F0;R1; gehören zu L_Roboter. Ein DEA muss nur endlich viele Phasen eines Befehls unterscheiden.

Geschachtelt: ein stärkeres Modell motivieren

W{F1;}, W{L0;W{R1;}} und W{W{F0;}} gehören zur Blocksprache; W{F1; und W{L0;}} nicht. Ein endlicher Automat kann die beliebig große Zahl noch offener Blöcke nicht vollständig speichern.

Das motiviert ein stärkeres Speicher- und Grammatikmodell. Eine konkrete Typ-2-Grammatik allein ist aber noch kein allgemeiner Beweis, dass ihre Sprache nicht regulär ist; ein solcher Beweis müsste ausdrücklich geführt werden.

Anschluss an Q3.3

Rekursion erzeugt unbeschränkt tiefe Struktur. Ein Kellerautomat ergänzt den endlichen Automaten deshalb um einen Stack: Beim Öffnen kann er Information ablegen, beim Schließen passend wieder abbauen.

Lernspur · Geschachtelte Roboterblöcke untersuchen

Diagnostiziere zuerst konkrete Blockwörter und entwickle dann selbst eine rekursive Grammatik.

Station 9 starten

Chomsky-HierarchieLK

Grammatikklassen, Sprachklassen und Speicherbedarf einordnen

Die Chomsky-Hierarchie ordnet Grammatik- und Sprachklassen danach, wie stark ihre Produktionen eingeschränkt sind. Stärkere Einschränkungen erzeugen kleinere Sprachklassen. Reguläre Sprachen sind deshalb Teil der kontextfreien Sprachen.

Inklusionsketten lesenTyp 3 ⊂ Typ 2 ⊂ Typ 1 ⊂ Typ 0

Klassen liegen ineinander

Typ 3 ⊂ Typ 2 ⊂ Typ 1 ⊂ Typ 0

Name: Strenge Inklusion in der Chomsky-Hierarchie.
So liest man: „Typ drei ist eine echte Teilmenge von Typ zwei, das ist eine echte Teilmenge von Typ eins, das ist eine echte Teilmenge von Typ null.“
Das bedeutet: Jede reguläre Sprache (Typ 3) ist auch kontextfrei (Typ 2); umgekehrt gilt das nicht immer.
Beispiel: Die flache Robotersprache ist regulär. Verschachtelte Roboterblöcke zeigen, warum eine stärkere Beschreibung nötig werden kann.
Nicht verwechseln: ⊂ zeigt hier eine echte Teilmenge. ⊆ bedeutet nur Teilmenge und erlaubt Gleichheit; die Kette ist weder Zeitfolge noch Schwierigkeitsrangliste.

Typ 3 ⊂ Typ 2 ⊂ Typ 1 ⊂ Typ 0 ist eine Inklusionsordnung.
Typ 3: regulär; passende Erkennung mit endlichen Automaten.
Typ 2: kontextfrei; passende Erkennung mit Kellerautomaten.
Typ 1: kontextsensitiv; Typ 0: rekursiv aufzählbar.

Die Hierarchie meint nicht pauschal, ein Modell sei „einfacher“. Sie vergleicht die notwendige Ausdrucks- und Speichermächtigkeit: Ein endlicher Automat reicht für Typ 3, ein Kellerautomat stellt für Typ 2 zusätzlichen Stack-Speicher bereit. Gefordert ist hier die begründete Einordnung, kein formaler Beweis.

Lerngrafik zur Chomsky-Hierarchie mit Typ 0 bis Typ 3 und zugeordneten Automatenmodellen — Die geschachtelten Mengen verbinden Produktionsbeschränkung, Sprachklasse und geeignete Maschinenmodelle.

Lernspur · Chomsky-Hierarchie begründen

Ordne die Blockgrammatik als Grammatikform ein und begründe danach eine Modellgrenze an einem neuen Strukturfall.

Station 10 starten

Sichern und vernetzen
Fachliche Synthese, Werkzeugverweise und Anschluss an Automaten

Gleiche Zeichen, andere Rolle{…} · | · (…) · * · + · → · Indizes

Diese Übersicht wiederholt keine vollständigen Erklärungen. Sie verweist auf den jeweiligen fachlichen Erklärort.

{…}: Mengenklammern beim Alphabet; als Wortzeichen in der Blockgrammatik.
|: Bedingungstrenner oder Wortlänge; als „oder“ bei Produktionen.
(…): geordnete Rollen im 4-Tupel; bei L(G) die zugehörige Grammatik.
* und +: Wortmengenoperatoren, keine Rechenoperationen.
→: Produktionspfeil; als konkreter Schritt bei Ableitungen und als Zustandswechsel bei Automaten.
Indizes nummerieren Namen oder Muster; ; bleibt dagegen ein tatsächlich zu lesendes Terminalzeichen.

Werkzeuge und Anschluss

Die Inhaltsseite erklärt Begriffe und Modelle. Die Lernspur führt schrittweise durch Q3.1; die bestehenden Fachreihen dienen der Vertiefung und Prüfung. Beide Werkzeuge bleiben getrennte fachliche Arbeitsräume.

Lernen: Lernspur – Schritt für Schritt Vertiefen und prüfen: FS-Reihen Frei arbeiten: Formalsprachen Q3.2-Anschluss: Automaten

Fachlich verdichtete Merksätze

Σ* enthält alle endlichen Wörter über dem Alphabet; L ⊆ Σ* wählt die syntaktisch zulässigen Wörter aus.
Syntax beschreibt die Form; Semantik und Ausführung betreffen Bedeutung und Situation.
G = (N, T, P, S) trennt Nicht-Terminale, Terminale, Produktionen und Startsymbol.
L(G) umfasst genau die Terminalwörter, die vom Startsymbol regelkonform abgeleitet werden können.
Reguläre Grammatiken passen zu endlichen Automaten; kontextfreie Grammatiken können rekursiv geschachtelte Strukturen ausdrücken.

Anschluss an Q3.2 und Q3.3

Eine Grammatik erzeugt Wörter. In Q3.2 erkennt ein endlicher Automat Wörter regulärer Sprachen. In Q3.3 erweitert ein Kellerautomat die Erkennung um einen Stack, damit geschachtelte kontextfreie Strukturen verarbeitet werden können.