Dein Fortschritt:
0 / 0 Aufgaben
1
Die Kennwortregel
13 BEAFB I–IIDer Anmeldeserver einer Schule prüft einen Teil der Kennwortregel mit dem abgebildeten DEA \(A\) über \(\Sigma=\{b,\,z\}\). Vor der Prüfung wird jeder Buchstabe durch b und jede Ziffer durch z ersetzt; aus Mai24x wird so bbbzzb.
DEA A der Kennwortprüfung
- Ermitteln Sie für die Wörter \(\varepsilon\),
b,zb,bzb,zbz,bbzzbbjeweils den Zustand nach dem letzten Zeichen und entscheiden Sie, ob das Wort akzeptiert wird. (3 BE) - Ordnen Sie den drei Zuständen jeweils eine der folgenden Bedeutungen zu und begründen Sie eine Zuordnung am Graphen: „Ziffer schon gelesen, zuletzt ein Buchstabe“ · „noch keine Ziffer gelesen“ · „zuletzt eine Ziffer gelesen“. (3 BE)
- Formulieren Sie die von \(A\) akzeptierte Sprache \(L(A)\) in Worten und als Menge. Übersetzen Sie die Bedingung in eine Kennwortregel. (4 BE)
- Begründen Sie, dass jedes abgelehnte Wort durch Anhängen von höchstens zwei Zeichen zu einem akzeptierten Wort wird, und erklären Sie damit, warum \(A\) keinen Fehlerzustand hat. (3 BE)
Hinweise
Hinweis zu Aufgabe a)
Das leere Wort endet im Startzustand. Nur z2 ist Endzustand.
Hinweis zu Aufgabe b)
Welcher Zustand wird verlassen, sobald die erste Ziffer kommt, und nie wieder betreten? Wohin führt jedes z?
Hinweis zu Aufgabe c)
Die Bedeutung des Endzustands ist die Bedingung. Mengenschreibweise: \(L(A)=\{\,w\in\Sigma^*\mid\dots\,\}\).
Hinweis zu Aufgabe d)
Probieren Sie, von jedem Zustand aus mit denselben zwei Zeichen z2 zu erreichen.