Aufgabenblock — AFB III
Begründen statt nur ausführen: Grammatiken und Kellerautomaten entwerfen, Behauptungen widerlegen, Grenzen beweisen, Vorschläge bewerten. Formulieren Sie Ihre Antwort vollständig, bevor Sie die Musterlösung aufklappen.
Eine Kommazahl besteht aus einem optionalen Vorzeichen v, mindestens einer Ziffer z und optional einem Komma k, auf das mindestens eine Ziffer folgt, z. B. z, vzz, zkz, vzkzz. Entwerfen Sie eine reguläre Grammatik über T = {v, z, k}, geben Sie die Bedeutung jedes Nichtterminals an und testen Sie mit gültigen und ungültigen Wörtern.
Musterlösung anzeigen (zählt als erledigt)
T = {v, z, k}
Startsymbol: S
Produktionsregeln:
S → vA | zB
A → zB
B → zB | kC | ε
C → zD
D → zD | ε
| Nichtterminal | Bedeutung |
|---|---|
| S | noch nichts erzeugt |
| A | Vorzeichen erzeugt, Ziffer fehlt |
| B | mindestens eine Ziffer vor dem Komma — fertig möglich |
| C | Komma erzeugt, Ziffer fehlt |
| D | mindestens eine Ziffer nach dem Komma — fertig möglich |
| Testwort | Ergebnis |
|---|---|
vzkzz | S ⇒ vA ⇒ vzB ⇒ vzkC ⇒ vzkzD ⇒ vzkzzD ⇒ vzkzz ✓ |
z | S ⇒ zB ⇒ z ✓ |
v | nach vA keine ε-Regel ✗ |
zk | nach zkC keine ε-Regel ✗ |
zkzkz | D hat keine Regel mit k ✗ |
kz | S hat keine Regel mit k ✗ |
ε-Regeln nur bei B und D — genau dort darf die Zahl enden.
Jemand behauptet: „Jede Sprache, die eine kontextfreie Grammatik erzeugt, erkennt auch ein DEA — man braucht nur genug Zustände.“ Widerlegen Sie die Behauptung.
Musterlösung anzeigen (zählt als erledigt)
Gegenbeispiel: G mit S → aSb | ε ist kontextfrei und erzeugt \(L=\{a^nb^n\mid n\ge 0\}\).
Kein DEA: Hätte ein DEA k Zustände, würden zwei der Vorgeschichten \(a^0,\dots,a^k\), etwa \(a^i\) und \(a^j\) mit \(i<j\), im selben Zustand enden. Dann behandelt er \(a^ib^i\in L\) und \(a^jb^i\notin L\) gleich — Widerspruch. „Genug Zustände“ hilft nicht, weil das Argument für jedes k gilt.
Also: Jede reguläre Sprache ist kontextfrei, aber nicht umgekehrt.
Beweisen Sie, dass kein DEA die Sprache \(L=\{a^nb^{2n}\mid n\ge 0\}\) erkennt.
Musterlösung anzeigen (zählt als erledigt)
Annahme: Ein DEA A mit k Zuständen erkennt L.
Schubfach: Die k + 1 Vorgeschichten \(a^0, a^1, \dots, a^k\) enden in nur k Zuständen; zwei davon, \(a^i\) und \(a^j\) mit \(i<j\), im selben Zustand z.
Gleiches Urteil: Ab z liest A bei \(a^ib^{2i}\) und \(a^jb^{2i}\) dieselben Zeichen, endet also im selben Zustand — beide werden akzeptiert oder beide abgelehnt.
Widerspruch: \(a^ib^{2i}\in L\), aber \(a^jb^{2i}\notin L\), da \(2i\ne 2j\). Die Annahme ist falsch: Kein DEA erkennt L. (Ein Kellerautomat schafft es, siehe S → aSbb | ε.)