25.3 Determinierte endliche Automaten

Jetzt kommt ein Abschnitt, auf den sich alle Informatik-Schüler schon besonders "gefreut" haben, die formale Beschreibung eines determinierten endlichen Automaten. Eigentlich ist das nur für die Klausur- und Abitur-Leute wichtig, alle anderen können diesen Abschnitt gern "querlesen".

Formale Beschreibung eines DEAs

Diese Beschreibung hört sich auf den ersten Blick sehr abstrakt an, war daran liegen könnte, dass sie tatsächlich sehr abstrakt ist. Aber Sie sind auf der letzten Seite nach allen Regeln der didaktischen Kunst seelisch auf diese Definition vorbereitet worden. Betrachten Sie sich noch einmal die letzte Abbildung:

Determinierter endlicher Automat für double-Zahlen

Anhand dieser Abbildung soll die obige Definition erläutert werden.

Endliche Menge von Zuständen Q

Der Automat hat 5 Zustände, das ist sicherlich eine endliche Menge. Also können wir diese Menge definieren als Q = {1, 2, 3, 4, 5}.

Eingabealphabet S

Das Eingabealphebet dieses DEA besteht aus den Ziffern 0..9, den beiden Vorzeichen sowie dem Dezimalpunkt. Also gilt S = {0..9, +, -, .}

Übergangsfunktion δ

Die Übergangsfunktion beschreibt, mit welchem Zeichen aus dem Eingabealphabet man von einem Zustand in den nächsten Zustand kommt. Am einfachsten wird die Übergangsfunktion durch einen Graphen dargestellt, so wie wir ihn bisher auch verwendet haben. Alternativ kann man die Übergangsfunktion auch durch eine Tabelle beschreiben:

Startzustand q₀

Es gibt nur einen Startzustand, in unserem Beispiel ist dies der Zustand 1.

Endliche Menge von Endzuständen F

Es gibt mindestens einen Endzustand, aber auch mehrere Endzustände sind möglich. Für unser Beispiel gilt F = {3, 5}.

Sprache eines Automaten

Für ein Alphabet S bezeichnen wir mit S* die Menge aller endlichen Symbolfolgen über S, das ist die Menge aller Worte über dem Alphabet S einschließlich des leeren Wortes e.

Wendet man die Übergangsfunktion des Automaten für reelle Zahlen (Abb. 1) auf die Zeichenfolge "+12.5" an, so stoppt der Automat im Zustand 5. Dies ist einer der beiden Endzustände. Wird die Übergangsfunktion dagegen auf die Symbolfolge "+12." angewandt, so hält der Automat im Zustand 4, der nicht zu den Endzuständen gehört.

Diese Definition ist für angehende Informatiker im 3. oder 4. Semester gedacht, daher kann an dieser Stelle eine "Übersetzung" nicht schaden. Also, los geht's, und zwar in kleinen Schritten, die eigentlich jede(r) verstehen müsste.

Eingabealphabet S

S ist ja bekanntlich das Eingabealphabet des Automaten. Denken Sie an den Automaten für int-Zahlen, dort bestand das Eingabealphabet S aus der Menge {+, -, 0..9}. Das Eingabealphabet für den Automaten "Java-Bezeichner" bestand aus der Menge {a..z, A…Z, 0..9, _}, war also um Einiges größer.

Zeichenkette S*

Unter einer Zeichenkette $w \in S^{*}$ versteht man die Menge aller möglichen Kombinationen von Zeichen aus dem Eingabealphabet S. Wenn wir uns wieder den DEA für int-Zahlen anschauen, so wäre "+5+6+7+8" eine solche Zeichenkette aus dem Eingabealphabet. Auch "+57" wäre eine solche Zeichenkette, und natürlich auch "+++++".

Sie sehen sofort: Es gibt sinnvolle und auch sinnlose Zeichenketten, die aus dem Eingabealphabet gebildet werden können.

Wort

Dieser Begriff steht für eine "sinnvolle Zeichenkette". Die Definition, die so schwer zu verstehen ist, gibt nun genau an, welche der vielen möglichen Zeichenketten $w \in S^{*}$ sinnvolle Worte sind, und welche Zeichenketten eben nur sinnlose Zeichenketten sind. Sinnvolle Worte sind nur solche Zeichenketten, die den Automaten vom Startzustand q₀ in einen der Endzustände aus F überführen.

Sprache

Die Menge aller Worte eines DEAs wird auch als "Sprache des DEAs" bezeichnet. Wenn der DEA mit dem Symbol A (für Automat) bezeichnet wird, dann ist $L(A)$ die Sprache dieses Automaten (L ist die Abkürzung für language, engl. für Sprache).

Eng verwandt mit DEAs sind die regulären Ausdrücke. Man kann zu jedem DEA einen regulären Ausdruck konstruieren, der die gleiche Sprache beschreibt, und umgekehrt kann man zu jedem regulären Ausdruck einen DEA mit der gleichen Sprache konstruieren.

DEAs im NRW-Abitur

Im NRW-Abitur ist bisher fast jedes Jahr eine Klausuraufgabe zum Thema "Determinierte endliche Automaten" gestellt worden. Daher lohnt sich hier ein kurzer Blick auf eine kleine Auswahl solcher Aufgaben.

Aufgabe 2020

Diese Aufgabe habe ich auf einer Seite in www.abitur-informatik.de ausführlich beschrieben.

Aufgabe 2016

Hier soll ein DEA überprüfen, ob die Bestellungen in einer Pizzeria richtig eingegeben wurden. Dazu wird den Schülern die graphische Darstellung der Übergangsfunktion vorgegeben, die drei Endzustände sind hier durch doppelte Kreise markiert. Insgesamt hat der Automat fünf Zustände.

Die konkreten Aufgaben sahen wie folgt aus:

1. Die S. sollten ein Wort der Länge 7 und ein Wort mit minimaler Länge angeben, das vom Automaten als korrekt akzeptiert wird. Dann sollten die S. für zwei vorgegebene Worte die Abfolge der Zustände des DEAs angeben und entscheiden, ob die Worte zur Sprache des Automaten gehören.
2. In der zweiten Aufgabe sollten die S. das Eingabealphabet, die Menge der Zustände, den Startzustand und die Menge der Endzustände aus dem Diagramm entnehmen. Eine völlig simple Aufgabe, für die es sage und schreibe 10 Punkte gab. Für diese 10 Punkte sollten die S. allerdings auch die Bedeutung einiger spezieller Zustände erläutern.
3. Die dritte Teilaufgabe bezog sich dann auf ein anderes Thema, nämlich eine kontextfreie Grammatik. Darauf können wir an dieser Stelle noch nicht eingehen, das Thema wird erst in einer der nächsten Folgen behandelt.
4. In der vierten Teilaufgabe sollten die Bestellmöglichkeiten erweitert werden. Dazu wurde den S. eine tabellarische Darstellung der ersten Übergangsfunktion vorgegeben. Die S. sollten dann erläutern, welcher Zusamenhang zwischen der graphischen Darstellung und der Tabelle besteht, anschließend sollten sie die Tabelle nach den Vorgaben erweitern.
5. In der fünften Teilaufgabe mussten die S. begründen, wieso ein DEA nicht zählen kann.

Aufgabe 2015

In dieser Aufgabe ging es um Kommentare, wie sie in Programmiersprachen üblich sind. Den Schülenr wurde ein Zustandsübergangsgraph (also die graphische Darstellung der Übergangsfunktion) eines entsprechenden DEA vorgegeben. Dieser DEA hatte wieder mal fünf Zustände, davon drei Endzustände. Das Eingabealphabet war S = {/, *, #, z}, wobei z für ein beliebiges Zeichen steht.

Die konkreten Aufgaben:

1. Die erste Aufgabe war ähnlich wie die von 2016: Überprüfen eines vorgegebenen Wortes sowie Angeben von Worten, welche vom Automaten akzeptiert werden.
2. Auch die zweite Aufgabe ähnelte der von 2016: Die Rolle von zwei bestimmten Zuständen erläutern.
3. In der dritten Aufgabe sollte die graphische Darstellung der Übergangsfunktion in eine tabellarische Darstellung überführt werden.
4. Die vierte Aufgabe bestand darin, den Automaten etwas zu erweitern.
5. Die fünfte Aufgabe bezog sich wieder auf kontextfreie Grammatiken, auf die wir später noch eingehen werden.

Aufgabe 2014

Hier ging es um die "Blasensprache", die von einem Kaugummihersteller zu Werbezwecken entwickelt worden ist. Auch in dieser Aufgabe wurde den Schülern die graphische Darstellung der Übergangsfunktion (4 Zustände) sowie das Eingabealphabet vorgegeben.

Die Aufgaben:

1. Und wieder musste gezeigt werden, dass zwei vorgegebene Worte vom Automaten akzeptiert werden. Dann sollte die Graphik in eine Tabelle umgewandelt werden. Am Ende der ersten Teilaufgabe sollte der DEA in eine Grammatik umgewandelt werden, deren Sprache aus genau den Worten besteht, die der Automat akzeptiert.
2. In der zweiten Teilaufgabe wird eine Vereinfachung des DEA vorgeschlagen. Die S. sollten diesen Vorschlag analysieren.
3. Die dritte Teilaufgabe war interessant. Hier wurde den S. der Java-Quelltext einer Methode vorgegeben, die Zufallstexte erzeugte, die ungefähr der Sprache des Automaten entsprachen. Die S. sollten diesen Quelltext analysieren und angeben, welche Ausgabe er unter den gegebenen Bedingungen erzeugt. Auch sollte der Zusammenhang zwischen dem Quelltext und dem DEA aufgezeigt werden.
4. In der vierten Teilaufgabe sollte der Automat von den S. modifiziert werden.
5. Die fünfte Teilaufgabe behandelte wieder eine kontextfreie Grammatik, die ebenfalls "Blasensprache" erzeugt. Die S. sollten begründen, wieso diese Grammatik keine reguläre Grammatik ist, und sie sollten beschreiben, welche Worte von dieser Grammatik erzeugt werden können.

Diese kleine Auswahl von Aufgaben sollte genügen, um Ihnen zu zeigen, wie wichtig das Thema "Determinierte endliche Automaten" für das Zentralabitur in NRW ist und wie die Aufgaben in der Regel "gestrickt" sind.

Aufgabe 2007

Hier hatten die Schüler die Aufgabe, einen "Versetzungsautomaten" zu entwickeln. Gefüttert wurde dieser Versetzungsautomat mit Notenlisten, die absteigend sortiert waren, zum Beispiel:

5, 5, 4, 4, 4, 3, 3, 2

oder

5, 4, 4, 4, 3, 3, 2, 1

Die Schüler sollten nun einen DEA konstruieren, der nur Notenfolgen akzeptiert, die nach der "Versetzungsordnung" zu einer Versetzung führen. Die "Versetzungsordnung" war recht einfach:

• Mit einer Sechs: keine Versetzung
• Mit zwei (oder mehr) Fünfen: keine Versetzung
• Mit einer Fünf und nur Vieren: keine Versetzung
• Sonst: Versetzung

Der Automat sollte möglichst wenige Zustände haben, und er sollte bei einer Versetzung in einem Endzustand "landen".