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 Begriff⁹ 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.

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 eben­falls Zustände (hier q0 und q1), einen Startzustand (q0), ein Eingabealphabet (da es hier kein Ausgabe­alphabet gibt, schreibt man ∑ = {0, 1}) sowie Transi­tio­nen, 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är­zahlen, die auf 1 enden, z.B. 1, 1001, 1111, 000100101 – also genau die ungeraden. Gerade Binär­zahlen (die auf 0 enden) akzeptiert er hingegen nie. Da er also genau¹⁰ die ungeraden akzeptiert, ist er ein erkennen­der Automat für die Sprache der ungeraden Binärzahlen.

Gelegentlich haben Schüler die Fehlvorstellungen, dass aus einem Endzustand keine Transitionen mehr heraus­fü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 ver­mei­den, wenn im Unterricht passen­de Beispiele vorkommen, also DEA mit einem bzw. mehreren Endzuständen, Endzu­stän­de mit und ohne abgehende Transitionen.

Welche Wörter über {0,1} erkennt der DEA in Abbildung 3?¹¹

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

Am Übergangsgraphen bzw. der Transitionstabelle kann man auch nachprüfen, ob der Automat wirk­lich deter­ministisch ist: Dazu muss jede Transition mit einem Alphabetzeichen beschriftet sein, darf also nur nach einer Eingabe (aber nicht „spontan“) statt­finden. Zweitens darf es nie vorkommen, dass aus einem Zustand mehrere Übergänge mit der gleichen Eingabe heraus­führen. Gäbe es von q2 aus mehrere Transitionen mit 1, „wüsste“ der Auto­mat 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 akzeptie­ren­den Automaten eindeutig fest? Tatsächlich ist das nicht der Fall: Es gibt zu jeder Sprache viele Automaten, die diese Sprache erkennen.

Schon kleine DEAs können interessante Aufgaben lösen. Möchte man beispielsweise Mailadres­sen¹² 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 Domain­anga­be wie bbb.b.bb, wobei ein einzelnes Zeichen als Toplevel-Domain nicht in Frage kommt

(so dass die Wörter b.bbb@bbbb, bb.bb@bb.b, und bb.bb@ also unzulässig sind), dann kann ein DEA dieses Problem mit nur sieben Zuständen und 13 Transi­tionen lösen; ein handgeschrie­be­nes Java-Pro­gramm für die gleiche Aufgabe wäre aufwändiger, unübersichtlicher, damit fehleran­fäl­liger und vor allem bei Änderungen viel schwie­riger anzupas­sen.

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 Mailadres­sen) muss also gar nicht programmiert werden; stattdessen kann seine Übergangs­tabelle von einem DEA-Simulator benutzt werden, um den Mailadressen- (oder jeden anderen) DEA zu simu­lie­ren 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 Klammer­aus­drü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 Kellerautomaten¹³, die nicht nur Zustände, sondern zusätzlich einen Kellerspeicher (Stack) unbegrenzter Kapazität haben. Sie werden ab Seite 11 besprochen.

 

⁹ Auch im Deutschen wird oft das englische DFA für „deterministic finite automaton“ benutzt.

¹⁰ Betonungen werden in diesem Skript durch kursive Schrift angedeutet.

¹¹ 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.

¹² 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...

¹³ Statt Keller sagt man oft auch „Stapel“ oder „Stack“.

 

Hintergrundinformationen: Herunterladen [odt][669 KB]

 

Weiter zu Nichtdeterministische endliche Automaten NEAs