Die Fahrradstation
13 BEAFB I–IIAn einer Station für Leihfahrräder gibt es 3 Stellplätze. Jeder Vorgang wird protokolliert: r steht für eine Rückgabe (ein Rad mehr), l für eine Ausleihe (ein Rad weniger). Morgens ist die Station leer. Ein Protokoll über \(\Sigma=\{r,\,l\}\) heißt gültig, wenn zu keinem Zeitpunkt mehr als 3 oder weniger als 0 Räder in der Station stehen.
- Überprüfen Sie, welche der Protokolle
rrl,rrrr,lr,rlrrlgültig sind. (3 BE) - Zeichnen Sie den Zustandsgraphen eines DEA, der genau die gültigen Protokolle akzeptiert. (4 BE)
- Erläutern Sie, wie viele Zustände ein solcher DEA für eine Station mit \(k\) Stellplätzen benötigt, und warum sich dieses Vorgehen nicht auf eine (gedachte) Station ohne Obergrenze übertragen lässt. (4 BE)
- Die Stadt möchte nur Protokolle akzeptieren, die gültig sind und bei denen die Station am Ende wieder leer ist. Geben Sie an, wie Ihr DEA aus b) dafür geändert werden muss, und nennen Sie ein Protokoll, das dann zusätzlich abgelehnt wird. (2 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
rrl: 1, 2, 1 — gültigrrrr: 1, 2, 3, 4 — ungültig (vier Räder)lr: −1 — ungültig (Ausleihe aus leerer Station)rlrrl: 1, 0, 1, 2, 1 — gültig
Erwartungshorizont zu Aufgabe b)
zi bedeutet „i Räder in der Station“. Alle vier sind Endzustände, weil jedes bisher gültige Protokoll gültig ist; nur zF (nicht eingezeichnet) ist keiner.
Erwartungshorizont zu Aufgabe c)
Mögliche Radanzahlen 0, 1, …, \(k\): das sind \(k+1\) Zustände, dazu zF — insgesamt \(k+2\) Zustände. Für jede feste Zahl \(k\) ist das endlich.
Ohne Obergrenze kann die Radanzahl beliebig groß werden. Der Automat müsste jede Anzahl unterscheiden, denn nach \(n\) Rückgaben sind genau \(n\) Ausleihen erlaubt, nach \(n+1\) Rückgaben eine mehr. Das verlangt unendlich viele Zustände — ein DEA hat aber nur endlich viele.
Erwartungshorizont zu Aufgabe d)
Nur z0 bleibt Endzustand; z1, z2, z3 werden zu normalen Zuständen. Die Übergänge bleiben gleich. Zusätzlich abgelehnt wird z. B. rrl (am Ende steht noch ein Rad in der Station).
Geschachtelte HTML-Tags
17 BEAFB II–IIIEin Editor für Webseiten prüft, ob die Formatierungs-Tags <b> (fett) und <i> (kursiv) korrekt geschachtelt sind. Er betrachtet nur die Tags und ignoriert den Text dazwischen; das Eingabealphabet ist also \(\Sigma=\{\)<b>, </b>, <i>, </i>\(\}\).
Korrekt geschachtelt heißt: Jedes schließende Tag schließt das zuletzt geöffnete, noch offene Tag derselben Art, und am Ende ist kein Tag mehr offen.
- Ordnen Sie die Tag-Folgen
<b> <i> </i> </b>,<b> <i> </b> </i>,<i> </i> <b> </b>,</b> <b>den Kategorien „korrekt geschachtelt“ und „nicht korrekt geschachtelt“ zu und begründen Sie jeweils kurz. (3 BE) - Beweisen Sie, dass kein DEA die Sprache aller korrekt geschachtelten Tag-Folgen erkennt. Es genügt, Folgen zu betrachten, die nur
<b>und</b>enthalten. (5 BE) - Der Editor soll zunächst nur Schachtelungstiefen bis 2 zulassen: Es dürfen höchstens zwei Tags gleichzeitig offen sein. Entwerfen Sie einen DEA für die korrekt geschachtelten Folgen mit höchstens Tiefe 2. Geben Sie ihn als Übergangstabelle mit der Bedeutung der Zustände an. (5 BE)
- Ein Entwickler argumentiert: „Echte HTML-Dateien sind immer endlich lang. Deshalb kann man ihre Schachtelung doch mit einem DEA prüfen.“ Erörtern Sie diese Aussage. (4 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
<b><i> und <i><b> verlangen unterschiedliche schließende Tags. Wie viele verschiedene Listen offener Tags der Länge 0, 1 und 2 gibt es?Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
<b> <i> </i> </b>: korrekt — innen wird<i>geschlossen, dann<b>.<b> <i> </b> </i>: nicht korrekt —</b>kommt, während<i>zuletzt geöffnet wurde (Überkreuzung).<i> </i> <b> </b>: korrekt — zwei nacheinander geschlossene Bereiche.</b> <b>: nicht korrekt —</b>schließt ein Tag, das nie geöffnet wurde.
Erwartungshorizont zu Aufgabe b)
Annahme: Ein DEA \(A\) mit \(k\) Zuständen erkennt die Sprache. Schreibe kurz \(o\) für <b> und \(s\) für </b>.
Die \(k+1\) Vorgeschichten \(o^0, o^1, \dots, o^k\) enden in nur \(k\) Zuständen (Schubfachprinzip): Zwei davon, \(o^i\) und \(o^j\) mit \(i<j\), enden im selben Zustand.
Hängt man an beide \(s^i\) an, liest \(A\) ab diesem Zustand dieselben Zeichen und endet im selben Zustand: \(A\) akzeptiert \(o^is^i\) genau dann, wenn es \(o^js^i\) akzeptiert.
Aber \(o^is^i\) ist korrekt geschachtelt, \(o^js^i\) nicht (es bleiben \(j-i\) Tags offen). Widerspruch — die Annahme ist falsch. (Die Teilsprache \(\{o^ns^n\mid n\ge0\}\) entspricht gerade \(\{a^nb^n\mid n\ge0\}\).)
Erwartungshorizont zu Aufgabe c)
| Zustand | <b> | </b> | <i> | </i> | Bedeutung |
|---|---|---|---|---|---|
| z0 | z1 | zF | z2 | zF | keine offenen Tags |
| z1 | z3 | z0 | z4 | zF | offen: <b> |
| z2 | z5 | zF | z6 | z0 | offen: <i> |
| z3 | zF | z1 | zF | zF | offen: <b>, <b> |
| z4 | zF | zF | zF | z1 | offen: <b>, <i> |
| z5 | zF | z2 | zF | zF | offen: <i>, <b> |
| z6 | zF | zF | zF | z2 | offen: <i>, <i> |
| zF | zF | zF | zF | zF | Fehler |
(→ Startzustand, doppelt unterstrichen: Endzustand.) Jeder Zustand steht für die Liste der offenen Tags (zuletzt geöffnetes rechts): \(1+2+4=7\) Zustände und zF. Nur z0 ist Endzustand, weil am Ende nichts mehr offen sein darf.
Erwartungshorizont zu Aufgabe d)
Pro: Legt man eine feste maximale Tiefe \(t\) fest, gibt es nur endlich viele Listen offener Tags. Wie in c) lässt sich dann ein DEA bauen; für jede konkrete, endliche Datei existiert eine ausreichende Tiefe.
Contra: Die Zahl der Zustände wächst exponentiell: Bei \(m\) Tag-Arten und Tiefe \(t\) sind es \(1+m+m^2+\dots+m^t\) Zustände (bei 100 HTML-Tags und Tiefe 20 astronomisch viele). Außerdem muss die Grenze vorher feststehen — eine Datei mit Tiefe \(t+1\) würde fälschlich abgelehnt. Die Sprache aller korrekt geschachtelten Dateien ist nach b) nicht durch einen DEA erkennbar.
Fazit: Die Aussage stimmt nur für eine vorher festgelegte Tiefe und ist praktisch unbrauchbar. Editoren prüfen die Schachtelung deshalb mit einem Programm, das die offenen Tags in einer Liste mit beliebiger Länge speichert — also mit unbeschränktem Speicher, den ein endlicher Automat nicht hat.