Theoretische Informatik/ Das Prinzip des Automaten

Aus Wikibooks
Zur Navigation springen Zur Suche springen

< Wikibooks:Abstellraum: Strukturwissenschaften

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

Einführendes Beispiel[Bearbeiten]

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[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]

...das übliche...

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)