Theoretische Informatik/ Das Prinzip des Automaten
< Wikibooks:Abstellraum: Strukturwissenschaften
Der Abschnitt gibt eine Definition und Motivation des Automatenbegriffs in der Informatik.
Einführendes Beispiel Bearbeiten
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 Bearbeiten
Elemente Bearbeiten
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 Bearbeiten
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? Bearbeiten
Beispiel Nichtdeterministisch Beispiel Nichtendlich
Verhalten von Automaten Bearbeiten
Den Automaten zum Laufen bringen
Zustandsübergänge Bearbeiten
Zustandsüberführungsfunktion
Konfigurationsübergänge Bearbeiten
Konfiguration
Wörter und Automaten Bearbeiten
Automaten verarbeiten Wörter Bearbeiten
'Kann mein Automat A das Wort 'Missisippi' verarbeiten?' 'Kann Automat A alle Wörter verarbeiten die Automat B kann?'
Automaten definieren Sprachen Bearbeiten
Beispiele: Autokennzeichen, ... Eine Sprache ist eine Menge von Wörtern (genaueres im nächsten Abschnitt)