Theoretische Informatik/ Das Prinzip des Automaten

< Wikibooks:Abstellraum: Strukturwissenschaften

Der Abschnitt gibt eine Definition und Motivation des Automatenbegriffs in der Informatik.

Einführendes Beispiel

Bild 01: Beispiel Cola-Automat. Grau: Start, Doppelrand: Ende

Automat im umgangssprachlichen Sinne: z.B. Colaautomat. 1 Flasche kostet 50 cent. Es werden 10, 20 und 50 cent Münzen akzeptiert. Jeder Münzeinwurf ändert den Zustand des Automaten: am Anfang ist der Geldeinwurf leer. Wird ein 20 cent Stück eingeworfen beträgt der Gezahlte Betrag 20 cent, wird danach noch ein 20 cent Stück eingeworfen beträgt er 40 cent bei weiteren 10 cent dann 50 cent. Es werden zur Vereinfachung einige Annahmen gemacht: es muss genau bezahlt werden (50 cent), es wird nur der Geldeinwurf des Automaten für einen Bezahlvorgang betrachtet, es gibt keinen Abbruch des Bezahlvorgangs.

Selbstverständlich können auch andere Münzen in beliebiger Reihenfolge gewählt werden, z.B. 10, 10, 10 und 20 cent oder ein 50 cent Stück. Diese Möglichkeiten lassen sich grafisch Darstellen wie in Bild 1.

Bild 1 zeigt alle Bezahlmöglichkeiten des Colaautomaten. Im Startzustand ist die Eingezahlte Summe 0 cent im Endzustand immer 50 cent.

Sprache des Automaten (Wörter 1.- 9.):

1. 10 10 10 10 10
2. 10 10 10 20
3. 10 10 20 10
4. 10 20 10 10
5. 20 10 10 10
6. 10 20 20
7. 20 10 20
8. 20 20 10
9. 50

Wie verändert sich der Automat

• bei einer Preiserhöhung auf 60 cent?
• wenn nur noch 10 und 50 cent Münzen akzepiert werden? Also 20er nichtmehr angenommen werden.
• wenn Überbezahlung akzeptiert wird? Z.B. Zahlung von 60 cent mit { 20, 20, 20 }
• maximal drei Münzen angenommen werden? Z.B. { 20, 20, 10 } aber nichtmehr { 20, 10, 10, 10 }

Beschreibung von Automaten

Elemente

Im obigen Beispiel haben wir einen Automaten Definiert. Hierzu haben wir folgende Elemente benutzt:

• Zulässige Münzen (10, 20, 50) diese heißen verallgemeinert das Alphabet A des Automaten
• Mögliche bereits einbezahlte Beträge, also 0, 10, 20, 30, 40, 50 cent. Diese heißen verallgemeinert die Zustände Z des Automaten
• Mögliche Reaktionen auf den Einwurf einer Münze, z.B. Zustand alt: 30, Einwurf: 10, Zustand neu: 40. Zusammen heißen diese verallgemeinert die Zustandsüberführungsfunktion ü: Z x A -> Z des Automaten.
• Einen Startzustand s (0 cent) und die Menge aller Endzustände E ( hier nur einer: 50 cent, es können aber auch mehrere sein). Am Ende der Verarbeitung befindet sich der Automat immer im Endzustand. (d.h. er kann während der Verarbeitung einen Endzustand durchlaufen ohne dort stoppen zu müssen)

Dies gibt zusammen ein Tupel ( A, Z, ü, s, E ) also ( Alphabet, Zustände, Überführungsfunktion, Startzustand, Endzustände ).

Notation: grafisch und textuell

Anmerkung: Die obige 'Funktion' ü, ist streng genommen keine Funktion, da sie zwar rechtseindeutig (zu jedem linken Element (z, a) gibt es höchstens ein rechtes (z)) aber nicht linksvollständig (zu jedem linken Element gibt es mindestens ein rechtes) ist. Diese allgemein übliche 'Schlamperei' wird dadurch ausgeglichen, dass Funktionen (im strengen Sinne - also die linksvollständige und rechtseindeutige Relationen) 'totale Funktionen' genannt werden.

Definition Deterministischer Endlicher Automat

Ein Deterministischer Endlicher Automat (DEA), ist ein Automat dessen Zustände jeweils nur einen nachfolgenden Zustand für jede Eingabe besitzen. D.h, dass der Automat durch eine Eingabe nicht gleichzeitig in mehreren Zuständen sein kann. Er ist das Gegenstück zum Nicht Deterministischen Automaten (NDA), sollte jedoch immer dazu fähig sein die gleiche Funktion erfüllen zu können. Für jeden NDA gibt es einen funktionsfähigen DEA, auch wenn dieser umständlicher realisiert werden müsste.

Was bedeutet Deterministisch und Endlich?

Beispiel Nichtdeterministisch Beispiel Nichtendlich

Verhalten von Automaten

Den Automaten zum Laufen bringen

Zustandsübergänge

Zustandsüberführungsfunktion

Konfigurationsübergänge

Konfiguration

Wörter und Automaten

Automaten verarbeiten Wörter

'Kann mein Automat A das Wort 'Missisippi' verarbeiten?' 'Kann Automat A alle Wörter verarbeiten die Automat B kann?'

Automaten definieren Sprachen

Beispiele: Autokennzeichen, ... Eine Sprache ist eine Menge von Wörtern (genaueres im nächsten Abschnitt)