Deterministische endliche Automaten DEA (BP Items 1 ,7, 8, 11, 15)
Da Mealy-Automaten deterministisch und (in der Anzahl ihrer Zustände) endlich sind, sind sie deterministische endliche Automaten oder DEA. Meistens ist mit diesem Begriff9 allerdings ein anderer Typ Automat gemeint, der keine Ausgabe, dafür aber sogenannte Endzustände hat. Die „Ausgabe“ eines solchen DFA besteht nur darin, ob er am Ende der Eingabe in einem seiner Endzustände stehenbleibt oder in einem „normalen“. Falls er in einem Endzustand stehenbleibt, sagt man „der Automat hat das Wort akzeptiert“ – sonst hat er es nicht akzeptiert.
Abbildung 2: Akzeptor für die Sprache der ungeraden Binärzahlen ZPG Informatik [CC BY-SA 4.0 DE], aus zpg_sprachenautomaten_hintergrund.odt
Damit eignen sich DEAs besonders dafür, ein Wort auf „Gültigkeit“, also auf Zugehörigkeit zu einer bestimmten Sprache zu prüfen. Man nennt sie daher auch Akzeptoren oder erkennende Automaten für eine Sprache; in Abgrenzung dazu sind Mealy- und Moore-Automaten Transduktoren, weil sie die Eingabe in eine andere Form überführen.
Genau wie ein Mealy-Automat hat der DEA in Abbildung 2 ebenfalls Zustände (hier q0 und q1), einen Startzustand (q0), ein Eingabealphabet (da es hier kein Ausgabealphabet gibt, schreibt man ∑ = {0, 1}) sowie Transitionen, die mit Alphabet(Eingabe-)zeichen beschriftet sind. Gegenüber den Mealy-Automaten kommt für die formale Beschreibung eines DEA noch die Menge E ⊆ Q Endzustände hinzu, hier E={q1}.
Endzustände werden üblicherweise doppelt umrandet dargestellt wie hier q1.
Überzeugen Sie sich, dass dieser Automat genau dann in q1 steht, wenn unmittelbar vorher eine 1 gelesen wurde, sonst aber in q0. Falls die Eingabe in diesem Moment endet, wird sie also „akzeptiert“. Endet sie noch nicht, arbeitet der DEA weiter. Insgesamt akzeptiert er alle Binärzahlen, die auf 1 enden, z.B. 1, 1001, 1111, 000100101 – also genau die ungeraden. Gerade Binärzahlen (die auf 0 enden) akzeptiert er hingegen nie. Da er also genau10 die ungeraden akzeptiert, ist er ein erkennender Automat für die Sprache der ungeraden Binärzahlen.
Abbildung 3: Erweiterung des obigen DFA. Beim mit 1/0 doppelt beschrifteten Übergang handelt es sich genau genommen um zwei einzelne Übergänge. ZPG Informatik [CC BY-SA 4.0 DE], aus zpg_sprachenautomaten_hintergrund.odt
Gelegentlich haben Schüler die Fehlvorstellungen, dass aus einem Endzustand keine Transitionen mehr herausführen dürften („da ist er doch schon fertig?“), oder dass DEA mit mehreren Endzuständen irgendwie „mehrdeutig“ seien. Tatsächlich ist beides erlaubt und oft auch sinnvoll: es kommt nur darauf an, wo der DEA gerade steht, wenn die Eingabe endet. Diese Fehlvorstellungen lassen sich vermeiden, wenn im Unterricht passende Beispiele vorkommen, also DEA mit einem bzw. mehreren Endzuständen, Endzustände mit und ohne abgehende Transitionen.
Welche Wörter über {0,1} erkennt der DEA in Abbildung 3?11
Schülerinnen müssen auch DEA sowohl als Übergangsgraph darstellen, als auch formal korrekt beschreiben können. Diese Beschreibung umfasst am Beispiel
- das Eingabealphabet ∑ = {0, 1},
- die Menge ℤ = {q0, q1, q2, q3, qF} der Zustände,
- den Startzustand s = q0
- die Menge E der Endzustände, hier E={q3}
- die Transitionstabelle
| Eingabe → alter Zust. ↓ |
0 | 1 | |
| q0 | q0 | q1 |
Bemerkung: In der Tabelle muss er nur aufgeführt werden, falls Transitionen aus einem „normalen“ Zustand dorthin führen; in diesem Beispiel dürfte er auch weggelassen werden. |
| q1 | q0 | q2 | |
| q2 | q0 | q3 | |
| q3 | q3 | q3 | |
| qF | qF | qF |
Am Übergangsgraphen bzw. der Transitionstabelle kann man auch nachprüfen, ob der Automat wirklich deterministisch ist: Dazu muss jede Transition mit einem Alphabetzeichen beschriftet sein, darf also nur nach einer Eingabe (aber nicht „spontan“) stattfinden. Zweitens darf es nie vorkommen, dass aus einem Zustand mehrere Übergänge mit der gleichen Eingabe herausführen. Gäbe es von q2 aus mehrere Transitionen mit 1, „wüsste“ der Automat sonst nicht, welche davon er nehmen soll. Er müsste sozusagen „raten“; der Zufall darf bei deterministischen Automaten aber keine Rolle spielen.
Da ein DEA jedes Wort entweder akzeptiert oder nicht, legt er damit genau eine Sprache fest, eben die Menge der akzeptierten Wörter.
Lassen Sie die Schüler diskutieren, ob auch die Umkehrung gilt: Legt jede Sprache ihren akzeptierenden Automaten eindeutig fest? Tatsächlich ist das nicht der Fall: Es gibt zu jeder Sprache viele Automaten, die diese Sprache erkennen.
Abbildung 4: DFA für eine didaktisch sehr stark vereinfache Erkennung von Mailadressen. Zugunsten der Lesbarkeit werden Buchstaben hier durch ein „b“ und die im Diagramm schlecht erkennbaren Punkte durch „Punkt“ repräsentiert. [CC BY-SA 4.0 DE], aus zpg_sprachenautomaten_hintergrund.odt
Schon kleine DEAs können interessante Aufgaben lösen. Möchte man beispielsweise Mailadressen12 darauf prüfen, ob sie
- mit einem Benutzernamen beginnen (der eine Kombination aus Buchstaben und Punkten sein darf),
- dann ein @ enthalten
- und eine mindestens zweistufige Domainangabe wie bbb.b.bb, wobei ein einzelnes Zeichen als Toplevel-Domain nicht in Frage kommt
Wie wir auf Seite 3 gesehen hatten, ist dabei die Erkennung von Mailadressen selbst in LibreOffice noch etwas primitiver als dieser DEA.
Der Charme eines DEA ist, dass er anhand der Übergangstabelle simuliert werden kann, sobald die vollständige Beschreibung vorliegt. Ein DEA für eine bestimmte Aufgabe (etwa Mailadressen) muss also gar nicht programmiert werden; stattdessen kann seine Übergangstabelle von einem DEA-Simulator benutzt werden, um den Mailadressen- (oder jeden anderen) DEA zu simulieren und mit beliebigen Eingaben zu „füttern“. Diese Simulation kann in „Software und Programmierprojekte“ (Seite 26) selbst programmiert werden.
Für derartige Aufgaben empfiehlt es sich, das Alphabet wie hier einzuschränken, weil man dann nicht viele Pfeile für alle 26 Buchstaben zeichnen muss, sondern interessantere Fragen im Mittelpunkt stehen können.
Tatsächlich müssen in der Praxis letztlich weder DEA noch Übergangstabelle von Hand erstellt werden: Sie lassen sich aus einer textuellen Beschreibung (z.B. von gültigen Mailadressen) auch automatisch erzeugen, wenn die in Form sogenannter regulärer Ausdrücke vorliegt. Reguläre Ausdrücke werden ab Seite 17 behandelt.
Grenzen von DEAs
Allerdings gibt es auch Dinge, die DEAs nicht können: Obwohl das Problem nicht besonders schwierig klingt, misslingt beispielsweise schon der Versuch, damit korrekt geklammerte Rechenausdrücke zu erkennen: Ausdrücke, in denen alle geöffneten Klammern wieder richtig geschlossen werden. Der Ausdruck ((2+a)*((3+x)*2)-1)/5 etwa ist korrekt geklammert, (2+5))*3( hingegen nicht.
DEAs können solche Klammersprachen jedoch nicht erkennen: Um den korrekten Abschluss der Klammerung zu prüfen, müsste der Automat sich während der Verarbeitung des Wortes ja „merken“, wie viele Klammern gerade offen sind (in welcher Klammerungstiefe er sich also befindet). Einem DEA stehen als „Gedächtnis“ aber nur seine Zustände zur Verfügung. Ein Automat mit drei Zuständen kann also höchstens drei Klammerungsebenen unterscheiden und scheitert spätestens an der vierten; da jeder DEA eine endliche und vor allem feste Anzahl von Zuständen hat, ist prinzipiell kein DEA in der Lage, beliebig tief geschachtelte Klammerausdrücke zu überprüfen.
Da die Analyse derartiger rekursiv geschachtelter Strukturen aber häufig vorkommt, braucht man dafür ein mächtigeres Automatenmodell, und zwar die sogenannten Kellerautomaten13, die nicht nur Zustände, sondern zusätzlich einen Kellerspeicher (Stack) unbegrenzter Kapazität haben. Sie werden ab Seite 11 besprochen.
9 Auch im Deutschen wird oft das englische DFA für „deterministic finite automaton“ benutzt.
10 Betonungen werden in diesem Skript durch kursive Schrift angedeutet.
11 Dieser Automat erkennt nicht mehr dieselbe Sprache wie der vorige: Außer den ungeraden Binärzahlen erkennt er auch Wörter, die „111“ enthalten. Diese Ziffernfolge führt ihn nämlich in den Endzustand q3, den er dann nicht mehr verlässt.
12 Mailadressen eignen sich gut als Beispiel für den Unterricht, weil sie (2020 noch) allen Schülern geläufig sind. In Wirklichkeit ist die Prüfung von Mailadressen noch viel komplizierter, weil viele Sonderfälle zu beachten sind; in Programmiererforen wird ausdrücklich davor gewarnt, Mailadressen mit selbst gestricktem Code prüfen zu wollen. Nach Norm (RFC 2822) sind im Usernamen nämlich nicht nur + oder Leerzeichen erlaubt, sondern sogar das @ – es muss allerdings mit einem Backslash „maskiert“ werden. Sehr viele, auch große Mailanbieter weigern sich aber, solche (nach RFC zulässigen!) Konten anzulegen. Vielleicht haben sie Bedenken, die Gültigkeitsprüfung sonst nicht richtig hinzubekommen...
13 Statt Keller sagt man oft auch „Stapel“ oder „Stack“.
Hintergrundinformationen: Herunterladen [odt][669 KB]
Weiter zu Nichtdeterministische endliche Automaten NEAs