Wie aus Zeichenmengen Sprachen entstehen, wie Grammatiken Wörter
erzeugen und was genau die Frage $w \in L$? bedeutet.
TL;DR
Ein Alphabet $\Sigma$ ist eine endliche Menge von Symbolen; ein Wort ist eine endliche Folge dieser Symbole, das leere Wort heißt $\varepsilon$.
$\Sigma^*$ enthält alle endlichen Wörter über $\Sigma$ (inklusive $\varepsilon$). Eine Sprache $L$ ist eine beliebige Teilmenge von $\Sigma^*$.
Das Wortproblem stellt für gegebenes $w$ und $L$ die Frage: gilt $w \in L$? Es ist die zentrale Entscheidungsfrage der Automaten- und Sprachtheorie.
Eine Grammatik $G = (V, \Sigma, P, S)$ erzeugt eine Sprache $L(G)$ durch schrittweise Ableitung von Produktionen ausgehend vom Startsymbol $S$.
In der Klausur werden Ableitungen gelesen und Zugehörigkeit argumentativ begründet — diese Seite enthält jetzt auch durchgerechnete Rechenaufgaben zum Trainieren.
Definitionen & Formalismen
Alphabet
Ein Alphabet $\Sigma$ ist eine endliche, nichtleere Menge von Symbolen (auch Zeichen genannt).
Das leere Wort $\varepsilon$ ist das eindeutige Wort der Länge 0. Es ist neutrales Element der Konkatenation: $\varepsilon \cdot w = w \cdot \varepsilon = w$.
Die Konkatenation zweier Wörter $u = u_1 \dots u_m$ und $v = v_1 \dots v_n$ ist die Aneinanderreihung $uv = u_1 \dots u_m v_1 \dots v_n$. Sie ist assoziativ, aber im Allgemeinen nicht kommutativ.
$u = ab,\ v = ba \Rightarrow uv = abba \neq baab = vu$
Sternhülle $\Sigma^*$ und $\Sigma^+$
Die Sternhülle (Kleene-Hülle) enthält alle endlichen Wörter über $\Sigma$. $\Sigma^+$ ist die positive Hülle ohne $\varepsilon$.
Gegeben eine Sprache $L$ (beschrieben durch Grammatik, Automat, Ausdruck ...) und ein Wort $w \in \Sigma^*$: entscheide, ob $w \in L$.
Eingabe: $(L, w)\ \to\ $ Ausgabe: ja / nein
Grammatik
Eine Grammatik ist ein Quadrupel $G = (V, \Sigma, P, S)$ mit endlichen Mengen Variablen $V$ (auch Nichtterminale), Terminale $\Sigma$ mit $V \cap \Sigma = \emptyset$, Produktionsmenge $P \subseteq (V \cup \Sigma)^* \times (V \cup \Sigma)^*$ und Startsymbol $S \in V$.
Produktion: $\alpha \to \beta$ mit $\alpha, \beta \in (V \cup \Sigma)^*$, $\alpha$ enthält mindestens ein Nichtterminal
Ableitung $\Rightarrow$ und $L(G)$
Es gilt $u\alpha v \Rightarrow u\beta v$, wenn $\alpha \to \beta$ in $P$. Die reflexiv-transitive Hülle heißt $\Rightarrow^*$. Die Sprache der Grammatik ist
$$L(G) = \{w \in \Sigma^* \mid S \Rightarrow^* w\}$$
also alle Wörter aus Terminalen, die aus $S$ in endlich vielen Schritten ableitbar sind.
Kernkonzepte & Vorgehen
Um zu entscheiden, ob $w \in L(G)$, versucht man $w$ durch schrittweises Anwenden der Produktionen zu erzeugen. Für die Klausur ist wichtig, das systematisch zu lesen und die Struktur einer gegebenen Ableitung nachzuvollziehen.
Alphabet und Variablen identifizieren. Wer ist Terminal, wer ist Nichtterminal? Nichtterminale werden meist groß, Terminale klein geschrieben. Diese Trennung entscheidet, ob ein Ableitungsschritt zulässig ist.
Startsymbol markieren. Jede Ableitung startet bei $S$. Beginnt eine gegebene Herleitung nicht mit $S$, ist sie ungültig.
Produktionen als Regeln lesen. Eine Regel $\alpha \to \beta$ darf in einem Zwischenwort an einer beliebigen Stelle angewandt werden, an der $\alpha$ als Teilwort vorkommt. $\alpha$ wird durch $\beta$ ersetzt, alles andere bleibt gleich.
Terminalität prüfen. Eine Ableitung ist erst dann abgeschlossen, wenn das Zwischenwort ausschließlich aus Terminalen besteht. Bleibt ein Nichtterminal übrig, ist das Wort nicht in $L(G)$.
Endlichkeit sicherstellen. Die Ableitung $S \Rightarrow^* w$ muss in endlich vielen Schritten enden. Unendliche oder abgebrochene Herleitungen liefern keine Zugehörigkeit.
Nicht-Zugehörigkeit begründen. $w \notin L(G)$ zeigt man durch strukturelle Argumente über die Produktionen (nicht durch Aufzählen aller Ableitungen). Typisch: Zählargument, Invarianten oder Pumping-Argumente.
Beispiel durchgerechnet
Beispiel — Grammatik für $a^n b^n$
Betrachten wir die Grammatik $G = (V, \Sigma, P, S)$ mit
Schritt 3: $aaSbb \Rightarrow aabb$ (Regel $S \to \varepsilon$, das mittlere $S$ wird durch das leere Wort ersetzt).
Da das Ergebniswort $aabb$ ausschließlich aus Terminalen besteht und wir es aus $S$ abgeleitet haben, gilt $aabb \in L(G)$. ✔
Teil 2 — Zeigen: $abab \notin L(G)$
Argumentation über die Struktur der Regeln: Jede Anwendung von $S \to aSb$ fügt links ein $a$ und rechts ein $b$ hinzu und lässt genau ein $S$ in der Mitte. Die einzige Terminierungsregel $S \to \varepsilon$ ersetzt dieses $S$ ohne weitere Symbole zu erzeugen. Ableitbare Wörter haben also die Form $a^n \cdot \varepsilon \cdot b^n = a^n b^n$. Das Wort $abab$ hat diese Form nicht (nach dem ersten $b$ folgt wieder ein $a$), also $abab \notin L(G)$. ✔
Teil 3 — Ableitungsbaum
S
/|\
a S b
/|\
a S b
|
ε
Der Baum liest sich von der Wurzel $S$ nach unten: jede Ebene entspricht einer Regelanwendung. Die Blätter, von links nach rechts gelesen, ergeben genau $aabb$.
Rechenaufgaben mit Lösung
Trainiere hier den Klausur-Modus: Aufgabe lesen, selbst probieren, dann Lösung aufklappen und Schritt für Schritt vergleichen. Alle Ableitungen sind vollständig ausgerechnet.
Aufgabe 1leicht
Gegeben sei die Grammatik $G_1 = (V, \Sigma, P, S)$ mit $V = \{S\}$, $\Sigma = \{a, b\}$ und Produktionen $P = \{S \to aSb,\ S \to \varepsilon\}$. Führe eine vollständige Linksableitung des Wortes $w = aaabbb$ durch. Notiere in jedem Schritt die angewandte Regel.
Lösung anzeigen
Schritt 1: Start beim Startsymbol: $S$. Wir haben $|w| = 6$ und die Struktur $a^3 b^3$, also müssen wir dreimal $S \to aSb$ anwenden und einmal $S \to \varepsilon$.
Schritt 2: Regel $S \to aSb$ auf das (einzige) $S$: $$S \Rightarrow aSb$$
Schritt 3: Regel $S \to aSb$ auf das mittlere $S$: $$aSb \Rightarrow aaSbb$$
Schritt 4: Regel $S \to aSb$ nochmals auf das mittlere $S$: $$aaSbb \Rightarrow aaaSbbb$$
Schritt 5: Regel $S \to \varepsilon$ auf das verbliebene $S$: $$aaaSbbb \Rightarrow aaabbb$$
Ergebnis: Das Wort $w = aaabbb$ ist in genau vier Ableitungsschritten aus $S$ abgeleitet. Alle Zeichen sind Terminale, also gilt $w \in L(G_1)$.
Aufgabe 2leicht
Gegeben sei die Grammatik $G_2$ mit $\Sigma = \{a, b\}$, $V = \{S\}$ und $P = \{S \to aS,\ S \to b\}$. Berechne die ersten fünf Wörter von $L(G_2)$ aufsteigend nach Länge und beschreibe $L(G_2)$ in Mengenschreibweise.
Lösung anzeigen
Schritt 1: Die Regel $S \to aS$ fügt links ein $a$ hinzu und behält $S$. Die Regel $S \to b$ terminiert mit einem $b$. Es gibt kein $S \to \varepsilon$, also enthält jedes Wort mindestens ein $b$ am Ende.
Schritt 2: Kürzeste Ableitung: $S \Rightarrow b$. Also $w_1 = b$, Länge 1.
Schritt 3: Eine Anwendung von $S \to aS$, dann $S \to b$: $S \Rightarrow aS \Rightarrow ab$. Also $w_2 = ab$, Länge 2.
Schritt 4: Zwei $a$-Regeln: $S \Rightarrow aS \Rightarrow aaS \Rightarrow aab$. Also $w_3 = aab$.
Schritt 5: Analog $w_4 = aaab$ und $w_5 = aaaab$.
Schritt 6: Tabelle der ersten fünf Wörter:
#
Wort
Länge
Ableitung
1
b
1
$S \Rightarrow b$
2
ab
2
$S \Rightarrow aS \Rightarrow ab$
3
aab
3
$S \Rightarrow aS \Rightarrow aaS \Rightarrow aab$
4
aaab
4
$S \Rightarrow aS \Rightarrow aaS \Rightarrow aaaS \Rightarrow aaab$
5
aaaab
5
4x $S \to aS$, dann $S \to b$
Ergebnis: $$L(G_2) = \{a^n b \mid n \geq 0\}$$
Aufgabe 3mittel
Seien $A = \{a, ab\}$ und $B = \{b, \varepsilon\}$ zwei endliche Sprachen über $\Sigma = \{a, b\}$. Berechne
$A \cdot B$ (Konkatenation),
$A^2 = A \cdot A$,
alle Wörter aus $A^*$ mit Länge $\leq 3$.
Lösung anzeigen
Schritt 1: Erinnerung: $X \cdot Y = \{xy \mid x \in X,\ y \in Y\}$. Bei Mengen werden Duplikate nur einmal gezählt.
Schritt 2 — $A \cdot B$: Alle vier Kombinationen $x \cdot y$ mit $x \in \{a, ab\}$, $y \in \{b, \varepsilon\}$:
$x$
$y$
$xy$
a
b
ab
a
$\varepsilon$
a
ab
b
abb
ab
$\varepsilon$
ab
$ab$ tritt zweimal auf, wird aber nur einmal gezählt. $$A \cdot B = \{a,\ ab,\ abb\}$$
Schritt 3 — $A^2 = A \cdot A$: Alle Paare $x_1 x_2$ mit $x_1, x_2 \in \{a, ab\}$:
$x_1$
$x_2$
$x_1 x_2$
a
a
aa
a
ab
aab
ab
a
aba
ab
ab
abab
$$A^2 = \{aa,\ aab,\ aba,\ abab\}$$
Schritt 4 — $A^*$ bis Länge 3: Es gilt $A^* = \bigcup_{n \geq 0} A^n$ mit $A^0 = \{\varepsilon\}$. Kürzeste Wörter aus $A$ haben Länge 1 ($a$) bzw. 2 ($ab$).
$A^3$ hat Mindestlänge 3 ($aaa$). Nur $aaa$ hat Länge $\leq 3$.
Ergebnis: Wörter aus $A^*$ mit Länge $\leq 3$: $$\{\varepsilon,\ a,\ ab,\ aa,\ aab,\ aba,\ aaa\}$$
Aufgabe 4mittel
Gegeben ist der reguläre Ausdruck $r = (a \mid b) \cdot a^*$. Liste alle Wörter aus $L(r)$ mit Länge $\leq 3$ auf. Sortiere zuerst nach Länge, dann alphabetisch.
Lösung anzeigen
Schritt 1: Struktur des Ausdrucks: Zuerst genau ein Zeichen aus $\{a, b\}$, danach beliebig viele (auch null) $a$-Zeichen. Formal: $L(r) = \{a, b\} \cdot \{a\}^*$.
Schritt 2 — Länge 1: Kein $a$ hintendran, also nur der erste Buchstabe: $a$, $b$.
Schritt 3 — Länge 2: Ein $a$ hintendran. Aus $a$: $aa$. Aus $b$: $ba$.
Schritt 4 — Länge 3: Zwei $a$ hintendran. Aus $a$: $aaa$. Aus $b$: $baa$.
Schritt 5: Wichtig: Der reguläre Ausdruck erzwingt genau einen Buchstaben am Anfang, also kein $\varepsilon$ in $L(r)$. Mindestlänge ist 1.
Schritt 6: Übersicht:
Länge
Wörter
1
a, b
2
aa, ba
3
aaa, baa
Ergebnis: $$L(r)_{\leq 3} = \{a,\ b,\ aa,\ ba,\ aaa,\ baa\}$$ Insgesamt sechs Wörter.
Aufgabe 5mittel
Gegeben sei $G_3$ mit $V = \{S\}$, $\Sigma = \{a, b\}$ und $P = \{S \to aSa,\ S \to bSb,\ S \to a,\ S \to b,\ S \to \varepsilon\}$ (Palindrom-Grammatik über $\{a,b\}$). Zeige für jedes der drei folgenden Wörter durch Angabe einer Ableitung, dass es in $L(G_3)$ liegt:
$w_1 = aba$
$w_2 = abba$
$w_3 = babab$
Lösung anzeigen
Schritt 1 — Strategie: Die Regeln bauen Palindrome von außen nach innen auf. Bei ungerader Länge endet man mit $S \to a$ oder $S \to b$ (mittleres Zeichen). Bei gerader Länge endet man mit $S \to \varepsilon$.
Schritt 5 — Sanity-Check: Alle drei Wörter sind tatsächlich Palindrome (von vorn und hinten gleich gelesen). Alle Ableitungen enden in reinen Terminalwörtern.
Ergebnis: $w_1, w_2, w_3 \in L(G_3)$. Als Nebenergebnis: $L(G_3) = \{w \in \{a,b\}^* \mid w = w^R\}$, also die Menge aller Palindrome über $\{a, b\}$.
Aufgabe 6schwer
Gegeben sei $G_4$ mit $V = \{S, A\}$, $\Sigma = \{a, b\}$ und
$P = \{S \to aAb,\ A \to aAb,\ A \to \varepsilon\}$.
(a) Berechne die ersten vier Wörter von $L(G_4)$ (nach Länge sortiert).
(b) Führe eine vollständige Linksableitung von $w = aaabbb$ durch.
(c) Beschreibe $L(G_4)$ in Mengenschreibweise.
Lösung anzeigen
Schritt 1 — Strukturanalyse: Aus $S$ gibt es nur eine Regel: $S \to aAb$. Also beginnt jedes Wort mit $a$ und endet mit $b$. Danach expandiert $A$ mittels $A \to aAb$ (Klammer-Aufbau) oder terminiert mittels $A \to \varepsilon$.
Schritt 6 — (c) Sprachbeschreibung: Jedes Wort in $L(G_4)$ hat die Form $a^n b^n$ mit $n \geq 1$ (das leere Wort ist nicht enthalten, weil $S$ zwingend erst $aAb$ produziert). Formal: $$L(G_4) = \{a^n b^n \mid n \geq 1\}$$
Ergebnis: $L(G_4) = \{a^n b^n \mid n \geq 1\}$. Unterschied zu $G_1$ aus Aufgabe 1: dort war $n \geq 0$ erlaubt und $\varepsilon \in L(G_1)$.
Aufgabe 7schwer
Sei $A = \{ab, ba\}$. Berechne $A^2$ und $A^3$ vollständig. Wie viele Wörter enthält jeweils $A^n$ für allgemeines $n \geq 0$? Begründe.
Lösung anzeigen
Schritt 1: Beide Wörter in $A$ haben Länge 2 und sind verschieden. Für $x_1, x_2 \in A$ ergibt $x_1 x_2$ ein Wort der Länge 4.
Schritt 2 — $A^2$:
$x_1$
$x_2$
$x_1 x_2$
ab
ab
abab
ab
ba
abba
ba
ab
baab
ba
ba
baba
Alle vier Ergebnisse sind paarweise verschieden. $$A^2 = \{abab,\ abba,\ baab,\ baba\},\quad |A^2| = 4$$
Schritt 3 — $A^3$: Es gibt $2^3 = 8$ Auswahlen $(x_1, x_2, x_3) \in A \times A \times A$. Jedes Ergebnis hat Länge $3 \cdot 2 = 6$. Wir konkatenieren explizit von links nach rechts:
Auswahl
Zwischenschritt
Wort (Länge 6)
ab · ab · ab
abab · ab
ababab
ab · ab · ba
abab · ba
ababba
ab · ba · ab
abba · ab
abbaab
ab · ba · ba
abba · ba
abbaba
ba · ab · ab
baab · ab
baabab
ba · ab · ba
baab · ba
baabba
ba · ba · ab
baba · ab
babaab
ba · ba · ba
baba · ba
bababa
Alle acht Ergebnisse sind paarweise verschieden. $$|A^3| = 8$$
Schritt 4 — Allgemeine Formel: Da die zwei Wörter in $A$ paarweise verschieden sind und keine Präfix-Überschneidungen produzieren (verschiedene Anfangsbuchstaben), ergibt jede $n$-Tupel-Auswahl aus $A$ ein eindeutiges Wort der Länge $2n$. Daher: $$|A^n| = 2^n \quad \text{für alle } n \geq 0$$
Was ist gefragt: Gegeben eine Grammatik und eine Kette von Zwischenwörtern $S \Rightarrow w_1 \Rightarrow w_2 \Rightarrow \dots \Rightarrow w_n$. Frage: welche Regel wurde in Schritt $i$ angewandt und an welcher Position?
So liest man das: Differenz von $w_i$ und $w_{i+1}$ markieren, im linken Teil ein Vorkommen von $\alpha$ suchen, das durch $\beta$ ersetzt wird.
Falle: Mehrere Positionen für dieselbe Regel sind möglich; es zählt diejenige, die die konkrete Änderung erklärt.
Typ B — Zugehörigkeit entscheiden
Was ist gefragt: Ist $w \in L(G)$? Begründung angeben.
So argumentiert man: Bei ja eine konkrete Ableitung angeben. Bei nein eine strukturelle Eigenschaft nennen, die alle ableitbaren Wörter erfüllen, $w$ aber nicht (z.B. gleiche Anzahl von $a$ und $b$, Reihenfolge, Palindromstruktur).
Falle: Ableitung, die mit einem Nichtterminal endet, gilt nicht als gültig.
Typ C — Sprache beschreiben
Was ist gefragt: Beschreibe $L(G)$ in Mengenschreibweise.
So liest man das: Rekursionsstruktur der Produktionen entschlüsseln, Anzahl und Reihenfolge der erzeugten Terminale aus jeder Regel ableiten, Muster in einer Formel $\{\dots \mid \text{Bedingung}\}$ festhalten.
Falle: $\varepsilon$ nicht vergessen, wenn eine $S \to \varepsilon$-Regel existiert.
Fragen zum Selbsttest
1. Was ist der Unterschied zwischen einem Alphabet $\Sigma$ und einer Sprache $L$?
$\Sigma$ ist eine endliche, nichtleere Menge einzelner Symbole. Eine Sprache $L$ ist dagegen eine Teilmenge von $\Sigma^*$, also eine (möglicherweise unendliche) Menge von Wörtern über diesem Alphabet. Kurz: $\Sigma$ enthält Zeichen, $L$ enthält Wörter aus diesen Zeichen.
2. Warum gilt $\varepsilon \in \Sigma^*$, aber $\varepsilon$ ist nicht dasselbe wie die leere Sprache $\emptyset$?
$\varepsilon$ ist ein Wort — nämlich das Wort der Länge 0. Als Wort ist es Element von $\Sigma^*$. Die leere Sprache $\emptyset$ hingegen ist eine Menge, die kein einziges Wort enthält. Die Sprache $\{\varepsilon\}$ enthält genau ein Wort und ist damit weder leer noch identisch mit $\varepsilon$.
3. Formuliere das Wortproblem in eigenen Worten und nenne die Ein- und Ausgabe.
Das Wortproblem fragt für eine Sprache $L$ und ein Wort $w$, ob $w$ zu $L$ gehört. Eingabe: Beschreibung von $L$ (Grammatik, Automat, regulärer Ausdruck) und ein Wort $w \in \Sigma^*$. Ausgabe: ja, falls $w \in L$, sonst nein.
4. Gegeben $P = \{S \to aSa,\ S \to bSb,\ S \to \varepsilon\}$. Ist $bab \in L(G)$?
Nein. Jede Regel fügt außen ein Zeichen paarweise gleich hinzu ($a\dots a$ oder $b\dots b$). Die ableitbaren Wörter sind daher Palindrome gerader Länge über $\{a, b\}$. $bab$ hat ungerade Länge, folglich $bab \notin L(G)$. (Als Nebenergebnis: $L(G)$ ist die Menge aller Palindrome gerader Länge über $\{a,b\}$.)
5. Lies folgende Ableitung. Welche Regel wurde in Schritt 2 verwendet? $S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb$ (Regeln: $S \to aSb$, $S \to \varepsilon$)
In Schritt 2 ($aSb \Rightarrow aaSbb$) wurde erneut die Regel $S \to aSb$ angewandt, und zwar auf das mittlere $S$. Schritt 3 ($aaSbb \Rightarrow aabb$) nutzt $S \to \varepsilon$.
6. Erkläre, warum die Menge $\Sigma^*$ immer abzählbar unendlich ist, sofern $\Sigma$ mindestens ein Symbol enthält.
$\Sigma^*$ ist als abzählbare Vereinigung $\Sigma^* = \bigcup_{n \in \mathbb{N}} \Sigma^n$ definiert. Jedes $\Sigma^n$ ist endlich (nämlich $|\Sigma|^n$ Wörter). Eine abzählbare Vereinigung endlicher Mengen ist abzählbar. Solange $|\Sigma| \geq 1$ ist, gibt es beliebig lange Wörter, daher ist $\Sigma^*$ nicht endlich, also abzählbar unendlich.
7. Kann eine Grammatik $G$ Wörter erzeugen, die Nichtterminale enthalten? Begründe.
Nein. $L(G) = \{w \in \Sigma^* \mid S \Rightarrow^* w\}$ ist per Definition auf Terminal-Wörter eingeschränkt. Zwischenformen mit Nichtterminalen sind zwar ableitbar, aber sie gehören nicht zur erzeugten Sprache. Ein Wort mit Nichtterminal ist keine gültige Antwort auf das Wortproblem.
8. Was ändert sich an $L(G)$, wenn die Regel $S \to \varepsilon$ entfernt wird und keine weitere Regel $S$ in $\varepsilon$ überführt?
Wenn $S \to \varepsilon$ gestrichen wird und keine andere Ableitungskette $S \Rightarrow^* \varepsilon$ möglich ist, verschwindet das leere Wort aus $L(G)$. Alle anderen Wörter, die vorher ableitbar waren, sind es weiterhin, sofern sie $S \to \varepsilon$ nicht als Zwischenschritt brauchen. In der Praxis muss man prüfen, ob Ableitungen ohne diese Regel noch terminieren können.
9. Warum ist Konkatenation im Allgemeinen nicht kommutativ, aber immer assoziativ?
Konkatenation reiht Symbole in gegebener Reihenfolge aneinander. $ab \cdot ba = abba$, aber $ba \cdot ab = baab$. Da die Reihenfolge zählt, ist sie nicht kommutativ. Assoziativität $(uv)w = u(vw)$ gilt hingegen, weil das Ergebnis nur von der Reihenfolge der einzelnen Symbole abhängt und Klammersetzung diese nicht verändert.
10. Zeige durch Argument, dass die Sprache $L = \{a^n b^n \mid n \geq 0\}$ nicht endlich ist.
Für jedes $n \in \mathbb{N}$ enthält $L$ das Wort $a^n b^n$. Verschiedene $n$ liefern verschiedene Wörter (schon durch verschiedene Länge $2n$). Da $\mathbb{N}$ unendlich ist, ist $L$ ebenfalls unendlich. Anmerkung: In späteren Kapiteln wird gezeigt, dass $L$ zwar kontextfrei, aber nicht regulär ist.
Dos & Donts in der Klausur
Dos
Alphabet, Variablen und Startsymbol explizit notieren, bevor du ableitest.
Jede Ableitung mit $S$ beginnen und mit einem reinen Terminalwort beenden.
Bei Nicht-Zugehörigkeit strukturell argumentieren (Invariante, Zählargument), nicht durch Fallunterscheidung raten.
$\varepsilon$ von $\emptyset$ und $\{\varepsilon\}$ sauber unterscheiden.
Bei Sprachbeschreibungen die Bedingung präzise formulieren ($n \geq 0$ vs. $n \geq 1$).
Donts
Nicht $\varepsilon$ mit einem Leerzeichen verwechseln — $\varepsilon$ ist ein Wort, kein sichtbares Zeichen.
Nicht eine Ableitung als abgeschlossen ansehen, solange noch ein Nichtterminal enthalten ist.
Nicht die Ableitungsrelation $\Rightarrow$ mit logischer Implikation verwechseln — $\Rightarrow$ ist ein Ersetzungsschritt.
Nicht behaupten, eine Sprache sei leer, nur weil $\varepsilon \notin L$. Endlichkeit und Leerheit sind verschiedene Aussagen.
Nicht die Reihenfolge in $G = (V, \Sigma, P, S)$ vertauschen — in der Klausur wird die exakte Quadrupel-Notation erwartet.