Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Wie beschreibt man verschachtelte Strukturen wie Klammern, Ausdrücke oder Programmiersprachen? Mit kontextfreien Grammatiken. Sie sind mächtiger als reguläre Ausdrücke und die Grundlage jedes Compilers (Parser). Klausurpflicht in 7/8 Theo-Inf-Modulen, oft mit Ableitungsbäumen und Mehrdeutigkeit.
Klausur-Tipp: Lies die Blätter eines Ableitungsbaums von links nach rechts, sie ergeben das erzeugte Wort. Für Mehrdeutigkeit musst du ZWEI strukturell verschiedene Bäume für dasselbe Wort finden, nicht nur zwei Ableitungs-Reihenfolgen.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
Wie beschreibt man verschachtelte Strukturen wie Klammern, Ausdrücke oder Programmiersprachen? Mit kontextfreien Grammatiken. Sie sind mächtiger als reguläre Ausdrücke und die Grundlage jedes Compilers (Parser). Klausurpflicht in 7/8 Theo-Inf-Modulen, oft mit Ableitungsbäumen und Mehrdeutigkeit.
Eine kontextfreie Grammatik erzeugt Wörter durch Regeln der Form „Variable → Zeichenfolge“. Man startet beim Startsymbol und ersetzt Variablen so lange, bis nur noch Terminalsymbole übrig sind.
Eine kontextfreie Grammatik (CFG) ist ein 4-Tupel G = (V, Σ, P, S):
| Symbol | Bedeutung |
|---|---|
| V | Variablen (Nichtterminale), meist Großbuchstaben |
| Σ | Terminale (das Alphabet der erzeugten Wörter) |
| P | Produktionen (Regeln) |
| S | Startsymbol (S ∈ V) |
Jede Produktion hat die Form A → α, mit EINER Variablen A links und einer beliebigen Folge α aus Variablen und Terminalen rechts.
Das „kontextfrei“ bedeutet: die linke Seite ist immer nur EINE Variable (unabhängig vom Kontext ersetzbar). Beispiel: S → aSb | ε (zwei Alternativen für S).
Beispiel S → aSb | ε: S ⇒ aSb ⇒ aaSbb ⇒ aabb. Diese Grammatik erzeugt L = { aⁿbⁿ | n ≥ 0 }.
Verschiedene Ableitungs-Reihenfolgen können zum SELBEN Ableitungsbaum führen, das ist KEINE Mehrdeutigkeit.
Ein Ableitungsbaum zeigt die Struktur einer Ableitung:
Eine Grammatik ist mehrdeutig, wenn es für mindestens ein Wort ZWEI verschiedene Ableitungsbäume gibt.
Klassisch: E → E+E | E*E | a erzeugt für a+a*a zwei Bäume (einmal + zuerst, einmal * zuerst). Das ist ein Problem für Compiler (welche Bedeutung?). Abhilfe: Grammatik mit Präzedenz und Assoziativität umschreiben.
Kontextfreie Sprachen sind Typ 2 der Chomsky-Hierarchie und eine ECHTE Obermenge der regulären Sprachen (Typ 3):
Jede reguläre Sprache ist kontextfrei, aber nicht umgekehrt. Beispiel: aⁿbⁿ ist kontextfrei, aber nicht regulär.
Das passende Maschinenmodell ist der Kellerautomat (Stack als zusätzliches Gedächtnis). Anwendungen: BNF/EBNF, Parser im Compilerbau.
1. CFG = 4-Tupel (V, Σ, P, S). Variablen, Terminale, Produktionen, Start.
2. Produktion: A → α, links GENAU eine Variable.
3. L(G) = alle aus S ableitbaren Terminalwörter.
4. Ableitungsbaum: Wurzel = S, Blätter = Wort.
5. Mehrdeutig = zwei Bäume für ein Wort (nicht zwei Reihenfolgen).
6. Kontextfrei (Typ 2) ⊋ regulär (Typ 3). aⁿbⁿ ist kontextfrei, nicht regulär.
1. Mehrdeutigkeit mit Ableitungs-Reihenfolge verwechseln. Links- vs. Rechtsableitung sind nur Reihenfolgen, kein Beweis für Mehrdeutigkeit. Es zählen verschiedene BÄUME.
2. Mehr als eine Variable links erlauben. Bei kontextfreien Grammatiken steht links GENAU eine Variable. Mehrere wären kontextsensitiv (Typ 1).
3. Regulär und kontextfrei gleichsetzen. Kontextfrei ist echt mächtiger: aⁿbⁿ ist kontextfrei, aber nicht regulär.
4. ε-Regel vergessen. Soll das leere Wort dazugehören, braucht man eine Regel wie S → ε.
5. Terminale und Variablen verwechseln. Variablen (Großbuchstaben) werden ersetzt, Terminale (Kleinbuchstaben/Σ) bleiben stehen und bilden das Wort.
6. Glauben, jede CFG sei eindeutig machbar. Manche kontextfreien Sprachen sind inhärent mehrdeutig: es gibt KEINE eindeutige Grammatik dafür.
Im ersten Tab leitest du das Wort aabb mit der Grammatik S → aSb | ε ab, der Ableitungsbaum wächst Schritt für Schritt. Im zweiten Tab siehst du die Mehrdeutigkeit der Ausdrucksgrammatik: für a+a*a gibt es zwei verschiedene Ableitungsbäume.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Lies die Blätter eines Ableitungsbaums von links nach rechts, sie ergeben das erzeugte Wort. Für Mehrdeutigkeit musst du ZWEI strukturell verschiedene Bäume für dasselbe Wort finden, nicht nur zwei Ableitungs-Reihenfolgen.
6 Aufgaben zu Produktionen, Ableitung und Bäumen.
Klausurfragen mit Lösungen (6)
Antwort: Genau eine Variable → beliebige Folge aus Variablen und Terminalen
Erklärung: Bei kontextfreien Grammatiken hat jede Produktion die Form A → α: links GENAU eine Variable (Nichtterminal), rechts eine beliebige Folge aus Variablen und Terminalen. Das „kontextfrei“ heißt, dass A unabhängig vom Kontext ersetzt werden darf. Klausur-Pflichtform.
Antwort: V, Σ, P, S (Variablen, Terminale, Produktionen, Startsymbol)
Erklärung: Eine CFG ist das 4-Tupel G = (V, Σ, P, S): V = Variablen (Nichtterminale), Σ = Terminale, P = Produktionen (Regeln), S = Startsymbol. (Q, Σ, δ, ... gehört zu Automaten.) Klausur-Pflichtdefinition.
Zuordnungen:
Erklärung: Variablen (Nichtterminale, Großbuchstaben) werden durch Regeln ersetzt. Terminale bleiben stehen und bilden das erzeugte Wort. Das Startsymbol ist die Wurzel jeder Ableitung. Im Ableitungsbaum ergeben die Blätter von links gelesen das Wort. Klausur-Pflicht-Zuordnung.
Typ: Zuordnung
Antwort: { aⁿbⁿ | n ≥ 0 } (gleich viele a wie b, a vor b)
Erklärung: S → aSb erzeugt bei jeder Anwendung links ein a und rechts ein b (verschachtelt), S → ε beendet. So entsteht aⁿbⁿ: gleich viele a wie b, alle a vor allen b. Diese Sprache ist kontextfrei, aber NICHT regulär. Klausur-Standardbeispiel.
Antwort: Wahr
Erklärung: RICHTIG. Mehrdeutigkeit bedeutet: für mindestens ein Wort existieren zwei strukturell verschiedene Ableitungsbäume. Nicht gemeint sind verschiedene Ableitungs-Reihenfolgen (Links- vs. Rechtsableitung), die zum selben Baum führen. Klausur-Definition.
Typ: Wahr/Falsch
Antwort: Sie ist mehrdeutig: a+a\*a hat zwei Bäume, also zwei mögliche Bedeutungen
Erklärung: Die Grammatik ist mehrdeutig: a+a\*a kann als (a+a)\*a oder a+(a\*a) interpretiert werden (zwei Ableitungsbäume). Ein Compiler wüsste nicht, welche Bedeutung gilt. Abhilfe: die Grammatik mit Präzedenz (\* vor +) und Assoziativität umschreiben, sodass sie eindeutig wird. Klausur-Transferfrage.
6 Klausur-Fragen zu Chomsky-Hierarchie, Mehrdeutigkeit und Sprachklassen.
Klausurfragen mit Lösungen (6)
Antwort: Typ 2
Erklärung: Kontextfreie Sprachen sind Typ 2 der Chomsky-Hierarchie. Typ 0 = rekursiv aufzählbar (Turing), Typ 1 = kontextsensitiv, Typ 2 = kontextfrei, Typ 3 = regulär. Es gilt: Typ 3 ⊊ Typ 2 ⊊ Typ 1 ⊊ Typ 0. Klausur-Einordnung.
Antwort: Kellerautomat (mit Stack)
Erklärung: Der Kellerautomat (Pushdown-Automat) erkennt genau die kontextfreien Sprachen. Sein Stack (Keller) ist das zusätzliche, unbegrenzte Gedächtnis, das ein endlicher Automat nicht hat, deshalb kann er z.B. aⁿbⁿ erkennen (a's auf den Stack, bei b's wieder runter). Klausur-Maschinenzuordnung.
Zuordnungen:
Erklärung: Typ 3 (regulär) = endlicher Automat. Typ 2 (kontextfrei) = Kellerautomat. Typ 1 (kontextsensitiv) = linear beschränkte Turing-Maschine. Typ 0 (rekursiv aufzählbar) = (allgemeine) Turing-Maschine. Je höher der Typ, desto mehr Gedächtnis/Modell-Stärke. Klausur-Pflicht-Zuordnung.
Typ: Zuordnung
Antwort: Jede reguläre Sprache ist kontextfrei, aber nicht umgekehrt
Erklärung: Die regulären Sprachen sind eine echte Teilmenge der kontextfreien: jede reguläre Sprache ist auch kontextfrei, aber es gibt kontextfreie Sprachen (z.B. aⁿbⁿ), die nicht regulär sind. Daher Typ 3 ⊊ Typ 2. Klausur-Hierarchie-Frage.
Antwort: Wahr
Erklärung: RICHTIG. Es gibt kontextfreie Sprachen, für die JEDE Grammatik mehrdeutig ist (inhärent mehrdeutig). Man kann sie also nicht durch Umschreiben eindeutig machen. Bei vielen praktischen Sprachen (z.B. arithmetische Ausdrücke) gelingt das Eindeutig-Machen aber durch Präzedenz/Assoziativität. Klausur-Vertiefung.
Typ: Wahr/Falsch
Antwort: Ein DFA hat nur endlich viele Zustände und kann n nicht beliebig groß zählen; der Kellerautomat nutzt seinen Stack als unbegrenzten Zähler
Erklärung: Für aⁿbⁿ muss man sich die Anzahl der a merken, um sie mit den b zu vergleichen. Ein DFA hat nur endlich viele Zustände, kann also nicht beliebig große n speichern (Pumping-Lemma beweist das). Der Kellerautomat legt jedes a auf den Stack und nimmt bei jedem b eines herunter, sein Stack ist unbegrenztes Gedächtnis. Klausur-Transferfrage.