Dein Fortschritt:
0 / 0 Aufgaben
1
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)
Führen Sie nach jedem Zeichen die Anzahl der Räder mit.
Hinweis zu Aufgabe b)
Jede mögliche Radanzahl 0 bis 3 wird ein Zustand. Welche Zustände sind Endzustände? Was passiert bei einer vierten Rückgabe?
Hinweis zu Aufgabe c)
Zählen Sie die möglichen Radanzahlen und denken Sie an den Fehlerzustand. Wie viele verschiedene Radanzahlen muss sich der Automat ohne Obergrenze merken?
Hinweis zu Aufgabe d)
Übergänge ändern sich nicht — nur eine Eigenschaft der Zustände.