Dos & Donts in der Klausur — Theoretische Informatik

Klausur-Relevanz: kritisch · Lesen UND Rechnen

Meta-Wissen für die Theo-Klausur: wie Aufgaben präzise gelesen, Beweise formal geführt und typische Fallen vermieden werden — die Klausur ist eine Lese- und Argumentationsprüfung, kein Programmierkurs. Diese Seite enthält jetzt auch durchgerechnete Rechenaufgaben im Klausur-Modus.

TL;DR

Die Klausur prüft Lesen, Argumentieren und formale Notation — nicht Code, nicht Kreativität, nicht Bauchgefühl.
Jeder Automat ist ein 5-Tupel (bzw. 6- oder 7-Tupel bei PDA/TM). Ein Diagramm allein ist keine vollständige Definition. Formal: $M = (Q, \Sigma, \delta, q_0, F)$.
Beweisen heißt: Vorannahme, Beweistechnik nennen, jeder Schritt begründet, Fazit sauber ausformuliert — nichts als trivial abtun.
Zeitmanagement: Aufgaben in aufsteigender Schwierigkeit lösen, unklare Stellen markieren, am Ende zurückkommen.
Bei Blackout: Definitionen niederschreiben, Beispiel skizzieren, Struktur erzwingen — Teilpunkte sind fast immer erreichbar.
Neu auf dieser Seite: vier durchgerechnete Meta-Rechenaufgaben (Fallen finden, Fehler markieren, Musterlösungsstruktur bauen, Zeitbudget kalkulieren).

1. Definitionen & Formalismen

Signalwörter der Aufgabenstellung

Die Verben in der Aufgabenstellung sind bindend. Sie legen fest, welche Beweistiefe erwartet wird.

beweisen Sie — vollständiger formaler Beweis mit Beweistechnik.
zeigen Sie — nahezu synonym zu beweisen; formale Argumentation nötig.
begründen Sie — Argumentation reicht, kein Vollbeweis, aber jede Aussage muss gestützt sein.
geben Sie an — Konstruktion oder Objekt liefern, ohne Beweis der Korrektheit.
skizzieren Sie — grober Ablauf, aber alle wesentlichen Ideen benennen.

Vollständige Angabe eines Automaten

Ein Diagramm ohne 5-Tupel ist unvollständig, weil Alphabet, Startzustand und Endzustandsmenge implizit bleiben.

DFA: $$M = (Q, \Sigma, \delta, q_0, F) \quad\text{mit}\quad \delta: Q \times \Sigma \to Q$$ NFA: dieselbe Form, aber $\delta: Q \times \Sigma \to \mathcal{P}(Q)$
PDA: $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ · TM: $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$

Formal korrekte Argumentation

Jede Aussage muss aus zulässigen Voraussetzungen folgen: Definition, Satz aus der Vorlesung, oder ein zuvor bewiesenes Zwischenresultat.

Kein offensichtlich, kein trivial, kein man sieht leicht ohne folgende Begründung. Formal: aus $A$ und $A \Rightarrow B$ folgt $B$ — jeder Pfeil braucht seine Regel.

2. Kernkonzepte / Vorgehen in der Klausur

Erste Runde — Überblick. Aufgabenblätter komplett durchblättern, Punktverteilung notieren, geschätzte Zeit pro Aufgabe kalkulieren (grobe Regel: $1\text{ Punkt} \approx 1{,}5\text{ Minuten}$ bei 90-Min-Klausur mit 60 Punkten). So vermeidest du, dass eine 4-Punkte-Aufgabe 25 Minuten frisst.
Aufgabenstellung präzise lesen. Verb unterstreichen (beweisen / zeigen / begründen / angeben). Objekt der Aufgabe identifizieren: geht es um eine Sprache $L$, um einen Automaten $M$, um eine Grammatik $G$? Was ist gegeben, was gesucht?
Reihenfolge wählen. Beginne mit Aufgaben, deren Typ du sicher kennst (Chomsky-Klassifikation, Automaten simulieren, Ableitungen nachvollziehen). Beweisaufgaben (Pumping-Lemma, Nichtabschluss) später, weil sie Kopf und Struktur brauchen.
Struktur vor Inhalt. Bei jedem Beweis zuerst das Gerüst hinschreiben: Beweistechnik nennen, Vorannahme, geplante Widerspruchsstelle. Dann füllen.
Notation sauber halten. Konfigurationsfolgen mit $\vdash$, Ableitungen mit $\Rightarrow$ und $\Rightarrow^*$, Sprache-Zugehörigkeit mit $w \in L(M)$. Mische Symbole nicht.
Zwischenschritte kommentieren. Ein einziges Wort pro Schritt reicht (nach Definition $\delta$, nach IV, Widerspruch zu Annahme). Korrektoren geben Teilpunkte für nachvollziehbare Zwischenschritte.
Fazit ausformulieren. Ein Beweis endet mit einem Satz: Also ist $L$ nicht regulär, q.e.d. Ohne diesen Satz wirkt der Beweis abgebrochen.
Blackout-Protokoll. Wenn nichts geht: Definition des zentralen Begriffs hinschreiben, ein einfaches Beispiel konstruieren, wieder zurück zur Aufgabe.

3. Beispiel durchgerechnet — eine Aufgabe präzise lesen

Gegebene Klausuraufgabe (fiktiv, typischer Klausurstil):

Aufgabe 3 (8 Punkte).
Sei L = { a^n b^n | n >= 0 }. Zeigen Sie mit dem Pumping-Lemma
fuer regulaere Sprachen, dass L nicht regulaer ist.
Geben Sie zusaetzlich eine kontextfreie Grammatik G mit L(G) = L an.

Schritt 1 — Lesen und Zerlegen

Zwei Teilaufgaben: (a) zeigen $\Rightarrow$ vollständiger Beweis, (b) angeben $\Rightarrow$ Grammatik hinschreiben, kein Beweis nötig.
Punkte grob aufteilen: 6 Punkte für den Beweis, 2 Punkte für die Grammatik.
Pumping-Lemma für reguläre Sprachen ist explizit vorgegeben — kein anderes Verfahren wählen.

Schritt 2 — Gerüst des Beweises

Beweis (Widerspruch mittels Pumping-Lemma).

Annahme: $L = \{a^n b^n : n \geq 0\}$ sei regulär.

Dann existiert eine Pumping-Zahl $n \in \mathbb{N}$, sodass für alle $w \in L$ mit $|w| \geq n$ eine Zerlegung $w = xyz$ existiert mit $|xy| \leq n$, $|y| \geq 1$ und $xy^i z \in L$ für alle $i \geq 0$.

Wähle $w = a^n b^n \in L$, $|w| = 2n \geq n$. Sei $w = xyz$ eine beliebige zulässige Zerlegung mit $|xy| \leq n$ und $|y| \geq 1$. Wegen $|xy| \leq n$ liegt $y$ komplett im $a$-Block: $$y = a^k \quad\text{mit}\quad 1 \leq k \leq n.$$ Betrachte $xy^2 z = a^{n+k} b^n$. Da $n + k \neq n$ (wegen $k \geq 1$), gilt $xy^2 z \notin L$. Widerspruch zum Pumping-Lemma. Also ist $L$ nicht regulär. $\blacksquare$

Schritt 3 — Grammatik angeben

$G = (V, \Sigma, P, S)$ mit $V = \{S\}$, $\Sigma = \{a, b\}$, Startsymbol $S$ und Produktionen $$P: \quad S \to a\,S\,b \mid \varepsilon.$$

Kommentar zum Beweis: Jeder Zwischenschritt hat eine kurze Rechtfertigung (nach Pumping-Lemma, nach Bedingung $|xy| \leq n$, Widerspruch zur Sprachdefinition). Der Beweis ist mit $\blacksquare$ / q.e.d. abgeschlossen. Bei der Grammatik ist alles vollständig angegeben — $V$, $\Sigma$, $P$, Startsymbol — nicht nur die Produktionen.

Falle: Wer nur $S \to aSb \mid \varepsilon$ hinschreibt, verliert Teilpunkte, weil die Grammatik als 4-Tupel $G = (V, \Sigma, P, S)$ definiert ist. Startsymbol und Alphabet müssen benannt sein.

4. Rechenaufgaben mit Lösung

Trainiere hier den Klausur-Modus: Aufgabe lesen, selbst probieren, dann Lösung aufklappen und Schritt für Schritt vergleichen. Diese vier Meta-Übungen ersetzen den Rechenaufgaben-Teil, den es für ein Meta-Thema in klassischer Form nicht gibt — Fokus: Fallen finden, Fehler markieren, Struktur bauen, Zeit kalkulieren.

Aufgabe 1 — Falle finden leicht

Gegeben sei folgende Klausuraufgabe:

Aufgabe 2 (6 Punkte).
Sei L = { w in {a,b}* : |w|_a = |w|_b }. Zeigen Sie,
dass L nicht regulaer ist. Geben Sie ausserdem einen
Kellerautomaten M mit L(M) = L an. Ein formaler Beweis
der Korrektheit von M ist nicht noetig.

Identifiziere drei Punkte, die man beim ersten Lesen leicht übersieht — was steht implizit drin, was ist Ablenkung, worauf zielt die Aufgabe genau?

Lösung anzeigen

Schritt 1: Verben zählen. Zwei Verben — zeigen und geben ... an. Also zwei Teilaufgaben. Wer nur eine bearbeitet, verliert mindestens die Hälfte der Punkte. Grobe Aufteilung: $\approx 4$ Punkte für den Nichtregularitätsbeweis, $\approx 2$ Punkte für den PDA.

Schritt 2: Implizite Information. $|w|_a$ bezeichnet die Anzahl der $a$-Zeichen in $w$. Diese Notation wird als bekannt vorausgesetzt. Sprache formal: $L = \{w \in \{a,b\}^* : |w|_a = |w|_b\}$. Nicht dieselbe Sprache wie $\{a^n b^n : n \geq 0\}$ — hier dürfen $a$ und $b$ beliebig gemischt sein.

Schritt 3: Ablenkung. Der Satz Ein formaler Beweis der Korrektheit von M ist nicht nötig ist eine Entlastung, keine Falle. Trotzdem muss der PDA vollständig als 7-Tupel angegeben werden — die Aussage bezieht sich nur auf den Korrektheitsbeweis, nicht auf die Vollständigkeit der Angabe.

Schritt 4: Zielsymbol Pumping. Da nach Nichtregularität gefragt ist, ist das Standardwerkzeug das Pumping-Lemma für reguläre Sprachen. Wortwahl: $w = a^n b^n$ funktioniert (liegt in $L$ und ist parametrisiert). Ein festes $w = aaabbb$ wäre ein klassischer Fehler.

Ergebnis: Die drei Fallen sind (a) zwei Teilaufgaben, nicht eine; (b) $|w|_a = |w|_b$ ist allgemeiner als $a^n b^n$, das Beispiel für den Beweis muss man selbst wählen; (c) PDA vollständig als 7-Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$, auch ohne Korrektheitsbeweis.

Aufgabe 2 — Fehler in Musterlösung markieren mittel

Ein Studierender gibt folgende Musterlösung für die Nichtregularität von $L = \{a^n b^n : n \geq 0\}$ ab. Markiere alle Fehler und begründe kurz, warum jeder Fehler Punktabzug kostet.

Beweis. L ist offensichtlich nicht regulaer, weil man
sich merken muss, wie viele a's gelesen wurden. Waehle
w = aaabbb. Nach Pumping-Lemma zerlegen wir w = xyz.
y liegt im a-Block. Pumpen wir y hoch, dann sind es mehr
a's als b's. Also nicht regulaer. Trivial. q.e.d.

Lösung anzeigen

Schritt 1: offensichtlich. Verbotene Formulierung ohne Begründung. Statt offensichtlich muss stehen: Wir zeigen mit dem Pumping-Lemma für reguläre Sprachen. Die informelle Intuition (man muss sich $n$ merken) ist keine formale Aussage.

Schritt 2: Wähle w = aaabbb. Ein festes Wort reicht nicht. Das Pumping-Lemma sagt: Es existiert eine Pumping-Zahl $n$, sodass für jedes $w \in L$ mit $|w| \geq n$ eine Zerlegung existiert. Um Nichtregularität zu zeigen, muss $w$ von $n$ abhängen: $w = a^n b^n$. Sonst bricht die Struktur des Widerspruchsbeweises zusammen.

Schritt 3: Zerlegen wir w = xyz. Fehlt die Bedingung $|xy| \leq n$ und $|y| \geq 1$. Nur weil diese Bedingung gilt, folgt, dass $y$ im $a$-Block liegt. Ohne die Bedingung ist die Fallunterscheidung nicht sauber.

Schritt 4: y liegt im a-Block. Behauptung ohne Begründung. Die Begründung wäre: Nach $|xy| \leq n$ liegt $xy$ vollständig in den ersten $n$ Zeichen von $w = a^n b^n$, also im $a$-Block. Somit auch $y$.

Schritt 5: Pumpen wir y hoch. Formal fehlt der Pumpfaktor $i$. Korrekt: Betrachte $xy^2 z = a^{n+k} b^n$ mit $k = |y| \geq 1$. Wegen $n + k \neq n$ gilt $xy^2 z \notin L$.

Schritt 6: Trivial. q.e.d. Das Wort trivial hat in einem formalen Beweis nichts zu suchen. Der Beweis endet mit einem sauberen Fazit: Also ist $L$ nicht regulär. $\blacksquare$

Ergebnis: Sechs Fehler, jeder einzeln punktrelevant. Reihenfolge der Verluste: fehlende Beweistechnikangabe, festes $w$ statt $w(n)$, fehlende Zerlegungsbedingungen, fehlende Begründung der Positionierung von $y$, unklares Pumpen, unsauberes Fazit. Grobe Schätzung: Von 6 Punkten bleiben etwa 1 bis 2.

Aufgabe 3 — Musterlösungsstruktur bauen mittel

Gegeben die Klausuraufgabe:

Aufgabe 4 (5 Punkte).
Sei L = { w in {0,1}* : w endet auf 01 }. Zeigen Sie,
dass L regulaer ist.

Gib eine Musterlösungsstruktur an: welche Notation muss vorkommen, in welcher Reihenfolge, was MUSS enthalten sein — ohne den kompletten Beweis auszuformulieren. Ziel: ein Skelett, das im Klausurstress abrufbar ist.

Lösung anzeigen

Schritt 1: Beweistechnik nennen. Einleitungssatz: Wir zeigen die Regularität von $L$ durch Angabe eines DFA $M$ mit $L(M) = L$. Warum reicht das? Weil eine Sprache genau dann regulär ist, wenn ein DFA sie akzeptiert (Charakterisierung durch endliche Automaten).

Schritt 2: 5-Tupel deklarieren. $$M = (Q, \Sigma, \delta, q_0, F)$$ mit expliziter Angabe aller fünf Komponenten:

$Q = \{q_0, q_1, q_2\}$ (drei Zustände: nichts gesehen, letztes Zeichen war $0$, letzte zwei Zeichen waren $01$)
$\Sigma = \{0, 1\}$
Startzustand: $q_0$
$F = \{q_2\}$
$\delta$ als Tabelle (siehe Schritt 3)

Schritt 3: $\delta$ als Tabelle.

$\delta$	$0$	$1$
$q_0$	$q_1$	$q_0$
$q_1$	$q_1$	$q_2$
$q_2$	$q_1$	$q_0$

Schritt 4: Diagramm optional. Nur wenn Zeit übrig. Diagramm ergänzt die Tabelle, ersetzt sie nicht.

Schritt 5: Kurze Korrektheitsargumentation. Ein Satz reicht: $M$ befindet sich in $q_2$ genau dann, wenn die zuletzt gelesenen zwei Zeichen $01$ sind. Damit gilt $\delta^*(q_0, w) \in F \iff w \text{ endet auf } 01 \iff w \in L$. Also $L(M) = L$.

Schritt 6: Fazit. Da $M$ ein DFA mit $L(M) = L$ ist, ist $L$ regulär. $\blacksquare$

Ergebnis (Skelett-Reihenfolge): (1) Beweistechnik nennen, (2) 5-Tupel, (3) $\delta$-Tabelle, (4) optional Diagramm, (5) einzeilige Korrektheit, (6) Fazit. Das ist die Struktur, die im Klausurstress abrufbar sein muss.

Aufgabe 4 — Zeitbudget kalkulieren leicht

Eine 90-Minuten-Klausur enthält 5 Aufgaben mit folgender Punkteverteilung:

Aufgabe 1: 8 Punkte  (Chomsky-Klassifikation)
Aufgabe 2: 12 Punkte (DFA konstruieren)
Aufgabe 3: 15 Punkte (Pumping-Lemma-Beweis)
Aufgabe 4: 10 Punkte (Grammatik + Ableitung)
Aufgabe 5: 15 Punkte (TM-Simulation)
Summe:     60 Punkte

Berechne (a) das Zeitbudget pro Aufgabe nach der Faustregel $1\text{ Punkt} \approx 1{,}5\text{ Minuten}$, (b) den Pufferrest, (c) eine sinnvolle Bearbeitungsreihenfolge inklusive Begründung.

Lösung anzeigen

Schritt 1: Faustregel prüfen. Grundregel: $\text{Zeit} = \text{Punkte} \times \frac{90\text{ min}}{60\text{ Punkte}} = \text{Punkte} \times 1{,}5\text{ min}$. Diese Regel gibt eine reine Punkteproportion, kein Puffer.

Schritt 2: Zeitbudget pro Aufgabe berechnen.

Aufgabe	Punkte	Rechnung	Zeit (min)
A1 (Chomsky)	8	$8 \cdot 1{,}5$	12
A2 (DFA)	12	$12 \cdot 1{,}5$	18
A3 (Pumping)	15	$15 \cdot 1{,}5$	22,5
A4 (Grammatik)	10	$10 \cdot 1{,}5$	15
A5 (TM)	15	$15 \cdot 1{,}5$	22,5
Summe	60		90

Schritt 3: Puffer bauen. Die Faustregel verbraucht die gesamten 90 Minuten. Für Lesen, Korrigieren und Übertragen sollten $\approx 10$ min Puffer bleiben. Also arbeite mit einem Skalierungsfaktor $s = \frac{80}{90} \approx 0{,}89$: $$\text{effektive Zeit} = 1{,}5\text{ min} \cdot s \approx 1{,}33\text{ min pro Punkt}.$$ Neue Werte (gerundet): A1: 11, A2: 16, A3: 20, A4: 13, A5: 20 (Summe: 80 min, Puffer: 10 min).

Schritt 4: Bearbeitungsreihenfolge festlegen. Regel: Sichere Punkte zuerst. Mögliche Reihenfolge:

A1 (Chomsky, 8P, 11 min) — Klassifikation ist Fließbandaufgabe, schnelle Punkte.
A4 (Grammatik + Ableitung, 10P, 13 min) — Ableitung ist mechanisch, Grammatik oft aus dem Kopf.
A2 (DFA konstruieren, 12P, 16 min) — Konstruktion, klare Struktur, wenig Beweislast.
A5 (TM-Simulation, 15P, 20 min) — Konfigurationsfolge Schritt für Schritt, wenig Kreativität.
A3 (Pumping-Lemma, 15P, 20 min) — höchster Kopfaufwand, ganz zum Schluss, mit Rest-Adrenalin.

Schritt 5: Notfall-Regel. Wenn eine Aufgabe das Budget um mehr als 30 Prozent überschreitet, abbrechen und weiter. Am Ende zurückkommen. Ein leeres Feld = 0 Punkte, ein halber Ansatz = oft 30 bis 40 Prozent.

Ergebnis: Zeitbudget pro Aufgabe A1..A5 ist 11, 16, 20, 13, 20 Minuten (mit 10 min Puffer). Reihenfolge: A1 $\to$ A4 $\to$ A2 $\to$ A5 $\to$ A3 (sichere Punkte zuerst, kognitiv teuerste Aufgabe zuletzt). Beweis- und Pumping-Aufgaben bewusst nach hinten, weil sie am meisten Kopf brauchen und am ehesten in Panik enden.

Aufgabe 5 — Bonus: Notationssünden entlarven schwer

Ein Studierender schreibt folgende Kette in einer TM-Simulation:

q0 011 -> 0 q1 11 => 01 q2 1 -> 011 q_accept

Finde alle vier Notationsfehler und schreibe die korrekte Konfigurationsfolge auf. Erwarte, dass die TM Zeichen von links nach rechts liest und im Endzustand $q_f$ akzeptiert.

Lösung anzeigen

Schritt 1: $\to$ vs $\vdash$. Für TM-Konfigurationsübergänge ist $\vdash$ (bzw. $\vdash^*$ für mehrere Schritte) die korrekte Notation. $\to$ ist Grammatikproduktion und darf hier nicht auftauchen.

Schritt 2: $\Rightarrow$. $\Rightarrow$ ist Grammatikableitung, keine Konfigurationsrelation. Auch dieses Symbol ist hier falsch. Es müssen alle Übergänge einheitlich mit $\vdash$ notiert sein.

Schritt 3: Konfiguration ohne Kopfposition. Eine TM-Konfiguration hat die Form $u\,q\,v$, wobei $q$ zwischen den Zeichen steht, die links bzw. rechts vom Kopf liegen. Die Zeichenkette $q_0$ 011 lässt offen, wo der Kopf steht. Konventionell steht der Kopf über dem ersten Zeichen: $q_0\,011$ mit Kopf auf der ersten $0$.

Schritt 4: $q_{\text{accept}}$ ohne Definition. Wenn die TM als $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ definiert ist, gehört der Endzustand zu $F$. Er heißt so, wie er im 5-/7-Tupel benannt wurde — meistens $q_f$ oder $q_{\text{acc}}$. Eigene Namen wie q_accept ohne Rückverweis auf $F$ sind ein Punktabzug.

Schritt 5: Korrekte Fassung. Angenommen die TM liest die Eingabe $011$, schreibt sie unverändert zurück und akzeptiert. Dann ist die Konfigurationsfolge $$q_0\,011 \;\vdash\; 0\,q_1\,11 \;\vdash\; 01\,q_2\,1 \;\vdash\; 011\,q_f$$ mit $q_f \in F$. Sauber: konsistentes $\vdash$, klare Kopfposition durch Zustandsplatzierung, Endzustand aus $F$.

Ergebnis: Vier Notationsfehler: (1) $\to$ statt $\vdash$; (2) $\Rightarrow$ statt $\vdash$; (3) fehlende Kopfposition durch unklare Konfigurationsschreibweise; (4) $q_{\text{accept}}$ statt $q_f \in F$. Korrekte Konfigurationsfolge $q_0\,011 \vdash 0\,q_1\,11 \vdash 01\,q_2\,1 \vdash 011\,q_f$.

5. Typische Klausurfragen — richtig lesen

Aufgaben-Typ A: Automat lesen und klassifizieren

Formulierung: Gegeben sei folgender Automat $M$. Bestimmen Sie $L(M)$ und geben Sie an, ob $L(M)$ regulär, kontextfrei oder rekursiv aufzählbar ist.

Was ist gefragt: Sprache benennen (Menge oder regulärer Ausdruck), Chomsky-Klasse angeben.
Wie lesen: Automatentyp am Kopf identifizieren (DFA / NFA / PDA / TM). Daraus folgt die kleinstmögliche Chomsky-Klasse.
Falle: Die Frage nach der Klasse ist meist die kleinste passende Klasse, nicht irgendeine. Ein DFA erkennt eine reguläre Sprache — aber reguläre Sprachen sind auch kontextfrei. Antwort: regulär.

Aufgaben-Typ B: Ableitung nachvollziehen

Formulierung: Geben Sie eine Ableitung von $w = aabb$ in $G$ an oder zeigen Sie, dass $w \notin L(G)$.

Was ist gefragt: Sequenz von Anwendungen der Produktionen mit $\Rightarrow$-Notation.
Wie lesen: Zwei mögliche Ausgänge — Ableitung existiert oder nicht. Beides mit Begründung.
Falle: Wer nur die letzte Ableitung schreibt, ohne die Zwischenschritte, verliert Punkte.

Aufgaben-Typ C: Konfigurationsfolge einer TM

Formulierung: Simulieren Sie die Berechnung der TM $M$ auf der Eingabe $011$. Geben Sie die Konfigurationsfolge an.

Was ist gefragt: Sequenz von Konfigurationen der Form $u\,q\,v$, verbunden mit $\vdash$.
Wie lesen: Bandinhalt sichtbar, Kopf zwischen zwei Zeichen als Zustand notiert.
Falle: Die TM akzeptiert, wenn sie in einen Endzustand gerät, nicht wenn sie hält. Genau lesen!

Aufgaben-Typ D: Nichtregularität zeigen

Formulierung: Zeigen Sie, dass $L$ nicht regulär ist.

Standardwerkzeug: Pumping-Lemma. Struktur wie im Beispiel oben.
Falle: Wortwahl $w$ muss von der Pumping-Zahl $n$ abhängen. Ein festes $w$ reicht nicht.

6. Fragen zum Selbsttest

Was ist der Unterschied zwischen den Verben beweisen, zeigen und begründen?

Beweisen und zeigen sind in Theo-Klausuren praktisch synonym und verlangen einen vollständigen formalen Beweis mit klar benannter Beweistechnik (direkt, Widerspruch, Induktion, Pumping-Lemma). Begründen erlaubt eine kürzere Argumentation, die zwar jede Aussage stützt, aber nicht in voller formaler Tiefe geführt werden muss. Angeben verlangt nur die Konstruktion des Objekts, ohne Korrektheitsbeweis — sofern nicht explizit anders verlangt.

Warum reicht ein Zustandsdiagramm eines DFA in der Klausur oft nicht aus?

Ein DFA ist per Definition ein 5-Tupel $M = (Q, \Sigma, \delta, q_0, F)$. Ein Diagramm zeigt implizit $Q$, $\delta$, $q_0$ und $F$, aber das Eingabealphabet $\Sigma$ bleibt oft mehrdeutig — sind Zeichen ohne ausgehende Kante Teil von $\Sigma$ mit einem Fehlerzustand oder gar nicht Teil von $\Sigma$? Wer $\Sigma$ nicht explizit angibt, verliert Punkte und macht die Definition mehrdeutig. Beste Praxis: Diagramm zeichnen und daneben das 5-Tupel notieren.

Was bedeutet die Notation $w \vdash^* w'$ im Kontext einer Turingmaschine?

$w \vdash^* w'$ bedeutet, dass die Konfiguration $w$ in null oder mehr Rechenschritten in die Konfiguration $w'$ übergeht. Das Sternchen ist der reflexive und transitive Abschluss der Ein-Schritt-Relation $\vdash$. Analoges gilt für PDA. Bei Grammatiken wird stattdessen $\Rightarrow^*$ verwendet — die Symbole werden nie vermischt.

Ist ein NFA, der ein Wort auf mindestens einem Berechnungspfad akzeptiert, ein akzeptierender Automat für dieses Wort?

Ja. Ein NFA akzeptiert ein Wort $w$ genau dann, wenn mindestens ein Berechnungspfad in einem akzeptierenden Zustand endet. Formal: $w \in L(M) \iff \exists\, \text{Pfad } \pi : \pi \text{ endet in } q \in F$. In der Klausur ist dies eine häufige Falle: Wer alle Pfade prüft und stoppt, sobald einer verwirft, urteilt falsch. Bei einem DFA hingegen ist der Pfad eindeutig, und Akzeptanz hängt allein vom Endzustand dieses eindeutigen Pfades ab.

Warum ist die Aussage $L$ ist nicht regulär, weil $L$ unendlich ist falsch?

Es gibt zahlreiche unendliche reguläre Sprachen — etwa $L = \{a^n : n \geq 0\}$, die von einem DFA mit einem Zustand und einer Schleife akzeptiert wird. Unendlichkeit ist keine hinreichende Bedingung für Nichtregularität. Die korrekte Argumentation nutzt das Pumping-Lemma oder den Myhill-Nerode-Satz und zeigt strukturelle Eigenschaften der Sprache, nicht ihre Kardinalität.

Wie identifiziert man in einer Aufgabenstellung die kleinstmögliche Chomsky-Klasse einer Sprache?

Zuerst prüft man Regularität mit Pumping-Lemma für reguläre Sprachen oder Myhill-Nerode. Scheitert das, versucht man Kontextfreiheit — entweder durch Angabe einer CFG oder eines PDA. Scheitert auch das, prüft man mit dem Pumping-Lemma für kontextfreie Sprachen die Nicht-Kontextfreiheit. Kontextsensitiv und rekursiv-aufzählbar folgen darüber. In der Klausur ist die kleinste Klasse gefragt, in der $L$ liegt.

Was bedeutet der Ausdruck $L(G) = L$ in einer Aufgabenstellung?

$L(G)$ ist die von der Grammatik $G$ erzeugte Sprache, definiert als die Menge aller terminalen Wörter, die aus dem Startsymbol ableitbar sind: $L(G) = \{w \in \Sigma^* : S \Rightarrow^* w\}$. Die Gleichung $L(G) = L$ verlangt zwei Inklusionen: $L(G) \subseteq L$ (Korrektheit der Grammatik) und $L \subseteq L(G)$ (Vollständigkeit). In der Klausur ist meist die Angabe von $G$ gefragt, aber wer den Nachweis führen muss, sollte beide Richtungen zeigen — idealerweise per Induktion über Ableitungslänge und Wortlänge.

Welche Klausurstrategie hilft bei einem Blackout während einer Beweisaufgabe?

Zuerst die Definition des zentralen Begriffs niederschreiben — allein das gibt oft schon Teilpunkte. Dann ein einfaches Beispiel konstruieren, das die Fragestellung illustriert. Danach den Beweisrahmen erzwingen: Annahme, Beweistechnik nennen, geplante Schritte skizzieren. Häufig kommt der inhaltliche Faden zurück, sobald die Struktur steht. Selbst ein unvollständiger, aber strukturierter Beweis ist deutlich mehr wert als ein leeres Blatt.

Warum sollte man in der Klausur nie triviale Schritte unbegründet weglassen?

Was für den Studierenden trivial erscheint, ist für den Korrektor nicht sichtbar. Die Formulierung offensichtlich oder trivial ersetzt keine Begründung — sie signalisiert eher, dass der Studierende die Rechtfertigung nicht kennt. Besser ist ein einzeiliger Verweis: nach Definition von $\delta$, nach Induktionsvoraussetzung, nach Abschlusseigenschaft der regulären Sprachen unter Vereinigung. Solche Kurzverweise geben volle Punkte.

Wie geht man mit einer Aufgabe um, die zwei Teilfragen enthält, von denen man nur eine sicher lösen kann?

Erst die Teilaufgabe lösen, in der man sicher ist, und deren Punkte vollständig einsammeln. Für die zweite Teilaufgabe zumindest die Struktur skizzieren: Definitionen aufschreiben, Ansatz benennen, ein Beispiel angeben. Teilpunkte sind fast immer erreichbar, und ein leeres Feld gibt garantiert null Punkte. Reihenfolge und Punktökonomie sind entscheidend.

7. Dos & Donts in der Klausur (themenspezifisch)

DO — Notation konsequent

Verwende $\Rightarrow$ für Grammatikableitungen, $\vdash$ für Konfigurationsübergänge, $\in$ für Sprachzugehörigkeit. Klar und einheitlich.

DONT — Symbole mischen

Nie $\to$ für Ableitung und Produktion gleichzeitig verwenden. $\to$ ist Produktion, $\Rightarrow$ ist Ableitungsschritt.

DO — Beweistechnik nennen

Am Anfang jedes Beweises steht: Beweis durch Widerspruch / durch vollständige Induktion / mittels Pumping-Lemma.

DONT — Beweis ohne Rahmen

Formeln aneinanderreihen ohne einleitenden Satz oder Fazit. Der Korrektor muss den roten Faden erkennen.

DO — Aufgabenstellung wörtlich zitieren

Bei Unsicherheit die Definition aus der Aufgabe abschreiben und darauf aufbauen. Das strukturiert die Antwort.

DONT — Aufgabenteil überlesen

Zwei Teilaufgaben in einer Aufgabe werden oft zusammengezogen, wobei die zweite komplett übersehen wird.

DO — Automat als 5-Tupel angeben

Diagramm zeichnen und daneben $M = (Q, \Sigma, \delta, q_0, F)$ ausschreiben. $\delta$-Funktion als Tabelle oder Kantenliste.

DONT — Nur Diagramm liefern

Ein alleinstehendes Diagramm lässt Alphabet und Endzustandsmenge offen und ist damit formal unvollständig.

DO — Zeit auf schwere Aufgaben begrenzen

Setze dir ein Zeitbudget pro Aufgabe. Beim Überschreiten weiter zur nächsten, später zurückkehren.

DONT — An einer Aufgabe festbeißen

30 Minuten an einer 4-Punkte-Aufgabe zu verlieren, während 20 Punkte auf dem letzten Blatt liegen, ist der klassische Klausurfehler.

DO — Wort $w$ von $n$ abhängen lassen

Beim Pumping-Lemma: $w$ muss mit der Pumping-Zahl $n$ parametrisiert sein, z.B. $w = a^n b^n$.

DONT — Festes $w$ wählen

Ein konkretes $w = aaabbb$ reicht nicht, weil das Pumping-Lemma für alle $w$ ab Länge $n$ gilt — die Beweisstruktur bricht zusammen.

Merksatz: Notation, Struktur, Fazit. Wer diese drei Dinge in jeder Aufgabe erfüllt, holt sich zuverlässig 70 Prozent der Punkte auch ohne perfekten Inhalt.

Warnung: Wer Aufgaben in Prosa löst, ohne formale Notation, riskiert selbst bei richtigem Ergebnis massive Punktabzüge. Theo ist eine formale Disziplin, keine Aufsatzprüfung.