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).
Erklärung
Kontextfreie Grammatiken
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.
Die Idee in einem Satz
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.
Die formale Definition
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) |
Die Form der Produktionen
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).
Ableitung und erzeugte Sprache
- Ein Ableitungsschritt (⇒) ersetzt eine Variable durch die rechte Seite einer Regel.
- Eine Ableitung ist eine Folge solcher Schritte vom Startsymbol bis zu einem Wort aus nur Terminalen.
- Die erzeugte Sprache L(G) ist die Menge aller so ableitbaren Terminalwörter.
Beispiel S → aSb | ε: S ⇒ aSb ⇒ aaSbb ⇒ aabb. Diese Grammatik erzeugt L = { aⁿbⁿ | n ≥ 0 }.
Links- und Rechtsableitung
- Linksableitung: in jedem Schritt wird die am weitesten LINKS stehende Variable ersetzt.
- Rechtsableitung: entsprechend die am weitesten rechts.
Verschiedene Ableitungs-Reihenfolgen können zum SELBEN Ableitungsbaum führen, das ist KEINE Mehrdeutigkeit.
Der Ableitungsbaum (Syntaxbaum)
Ein Ableitungsbaum zeigt die Struktur einer Ableitung:
- Wurzel: das Startsymbol.
- innere Knoten: Variablen.
- Blätter: Terminale (von links gelesen ergeben sie das Wort).
Mehrdeutigkeit
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 und die Chomsky-Hierarchie
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.
Klausur-Faustregeln
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.
Häufige Stolpersteine
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.
Interaktiv verstehen
Kontextfreie Grammatiken, interaktiv
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.
Praxis-Übung
Kontextfreie Grammatiken, Praxis-Übung
6 Aufgaben zu Produktionen, Ableitung und Bäumen.
Klausurfragen mit Lösungen (6)
- F1.Welche Form haben die Produktionen einer kontextfreien Grammatik?
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.
- F2.Aus welchen vier Komponenten besteht eine kontextfreie Grammatik?
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.
- F3.Ordne den Begriff seiner Bedeutung zu.
Zuordnungen:
- Variable (Nichtterminal) → wird ersetzt, meist Großbuchstabe
- Terminal → bleibt stehen, bildet das Wort
- Startsymbol → Wurzel jeder Ableitung
- Ableitungsbaum → Blätter ergeben das Wort
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
- F4.Welche Sprache erzeugt die Grammatik S → aSb | ε?
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.
- F5.Eine Grammatik ist genau dann mehrdeutig, wenn es ein Wort mit zwei verschiedenen Ableitungsbäumen gibt.
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
- F6.Warum ist die Ausdrucksgrammatik E → E+E | E\*E | a problematisch für Compiler?
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.
Klausur-Quiz
Kontextfreie Grammatiken, Klausur-Quiz
6 Klausur-Fragen zu Chomsky-Hierarchie, Mehrdeutigkeit und Sprachklassen.
Klausurfragen mit Lösungen (6)
- F1.Welcher Typ der Chomsky-Hierarchie sind die kontextfreien Sprachen?
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.
- F2.Welches Maschinenmodell erkennt genau die kontextfreien Sprachen?
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.
- F3.Ordne die Sprachklasse ihrem Chomsky-Typ + Modell zu.
Zuordnungen:
- Regulär (Typ 3) → endlicher Automat
- Kontextfrei (Typ 2) → Kellerautomat
- Kontextsensitiv (Typ 1) → linear beschränkte TM
- Rekursiv aufzählbar (Typ 0) → Turing-Maschine
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
- F4.Welche Aussage über reguläre und kontextfreie Sprachen ist korrekt?
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.
- F5.Manche kontextfreien Sprachen sind inhärent mehrdeutig, es gibt also keine eindeutige Grammatik für sie.
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
- F6.Warum kann ein endlicher Automat die Sprache aⁿbⁿ nicht erkennen, ein Kellerautomat aber schon?
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.
