Zur Themenwahl

Automaten

Schon in der Antike versuchten die Menschen Maschinen zu bauen, die ohne Eingriff des Menschen anscheinend ‘von selbst’ etwas bewegten. Daher kommt die Bezeichnung ‘Automat’. Diese Versuche wurden immer wieder aufgegriffen und führten z.B. zu mechanischen Schreibern und Schachspielern (diese zeigten sich allerdings als Betrugsversuche, weil in ihnen ein versteckter Mensch die Figuren führte). Mit der Entwicklung der Computer wurde die Problematik des Automatenbaus auf eine neue, allgemeine und abstrakte Ebene gehoben. Versucht man Maschinen, Geräte oder Systeme als Automaten zu klassifizieren, so hat sich die folgende Strukturbestimmung bewährt: Ein Automat ist durch drei Elemente charakterisiert: ein Automat kann verschiedene innere Zustände annehmen, es gibt eine Menge von Eingabemöglichkeiten, es gibt eine Menge von Automatenausgaben. Als Diagramm: Man sieht, dass von vielen speziellen Eigenschaften von Maschinen abgesehen wird und nur 3 Strukturelemente berücksichtigt werden. Der Erfolg einer solchen Einschränkung wird sich später bei der mathematischen Definition und Behandlung von Automaten zeigen. Unter dieses Schema lassen sich viele bekannte Maschinen, Geräte und vieles sonst bringen: Rechenmaschine, Toaster, Waschautomat, Cola-Automat, Computer, Taschenlampe, Baum, Lichtschalter, Auto, Mensch,.... Damit wird aber nicht gesagt, dass z.B. ein Mensch ein Automat ist; vielmehr wird angegeben, wie bestimmte Aspekte menschlichen Verhaltens als Automat beschrieben werden können. Und das mag zweckmäßig sein, wenn gerade diese genauer betrachtet werden sollen. Etwas ausführlichere Darstellung einiger Beispiele: Um die Funktionsweise eines Automaten komplett zu überblicken und ihn evtl. zu bauen, genügen solche Angaben nicht. Dafür muss genau angegeben werden, was bei welchen Atomatenzuständen und Eingaben passiert. Das führt zu einer mathematischen Beschreibung eines Auomaten. Ein Standardmodell für die Beschreibung von Automaten wird durch Mealy-Automaten geliefert.

Definition eines endlichen, deterministischen Mealy-Automaten

Ein Mealy-Automat ist ein 5-Tupel {X,Z,Y,λ, δ }. X ist eine Menge - die Eingabemenge mit den Elementen x, Y ist eine Menge - die Ausgabemenge mit den Elementen y, Z ist eine Menge - die Zustandsmenge des Automaten mit den Elementen z, λ ist eine Funktion von einer Teilmenge von X * Z → Y, δ ist eine Funktion von derselben Teilmenge von X * Z → Z. Die Mengen sind endlich (und nicht leer) und die Definitionsmengen von λ und δ sind gleich. Oft werden als Elemente der Mengen natürliche Zahlen gewählt. Übersichtlich kann ein Mealy-Automat in einer Tabelle dargestellt werden.

Zustandsreduktion von Automaten

Hat man einen Automaten über eine Tabelle (oder irgendwie sonst) definiert, so ist es sinnvoll zu untersuchen, ob man einen gleichwertigen Automaten bauen kann mit weniger Aufwand. Hierbei wird angenommen, dass ein Automat mit weniger Zuständen günstiger ist. Gleichwertig sollen dabei zwei Automaten sein, wenn sie die gleichen Mengen X und Y haben und bei einer beliebigen Folge von Eingabewerten x jeweils auch die gleiche Ausgabefolge von y-Werten liefern. Diese Forderungen legen es nahe, den Automaten in einer speziellen Tabelle darzustellen. Als Beispiel soll der Parkautmat dienen: Die Zelleninhalte sind Paare (Folgezustand z, Ausgabe y) also die Werte von λ und δ . Aus dieser Tabelle kann man in einfacher Weise den Zustandsgraph des Automaten gewinnen: Die Knoten stellen die Zustände dar. Die Pfeile geben den Übergang von einem Zustand zum andern an. Die Paare (x,y)sind jeweils Eingabe x und Ausgabe y. An einem weiteren Automatenbeispiel soll gezeigt werden, wie ein Automat zustands-reduziert wird zu einem Minimalautomaten. (Der Parkautomat ist schon reduziert, wie man schon an der Eingabe x = 1 sieht.) In der Tabelle prüft man die y-Ausgabenfolgen bei x-Eingabefolgen für alle Zustände z. Für die x-Folge 0 1 2 ... ergeben sich die folgenden y-Sequenzen z = 0: 3 2 0 ... z = 1: 1 0 1 ... z = 2: 0 1 3 ... z = 3: 2 1 3 ... z = 4: 2 1 3 ... z = 5: 0 3 1 ... z = 6: 1 2 0 ... Da (nur) die Zustände 3 und 4 dieselben y-Folgen haben, können sie zu einem Zustand 3’ zusammengefasst werden. Damit ergibt sich die Tabelle des reduzierten Automaten: Neben den Mealy-Automaten gibt es weitere, die spezielle Eigenschaften haben. Dazu gehören z.B. nichtdeterministische Automaten, bei denen Folgezustände nur mit einer bestimmten Wahrscheinlichkeit angenommen werden. Automaten können parallel oder gekoppelt betrieben werden. Man erhält dann Automatennetze. Zur Simulation von neuronalen Netzen wurden in den letzten Jahren zelluläre Automaten untersucht. Zelluläre Automaten sind aus vielen, einfachen Zellautomaten aufgebaut. Ihre Leistungsfähigkeit erhalten sie erst durch die Koppelung vieler solcher einfachen Automaten. Wir wollen im Folgenden zweidimensionale und eindimensionale zelluläre Automaten untersuchen.

Zweidimensionale Zelluläre Automaten

Stellt man sich ein unbegrenztes Schachbrett vor, so kann jedem einzelnen Feld ein Koordinatenpaar (i,j) zugeordnet werden. Auf diesen Feldern können Legesteine verteilt sein. Diese Legesteine können verschiedene Farben (Zustände) haben. Es wird eine Einfluss-Umgebung festgelegt, d.h. zu einem (beliebigen) Feld (i,j) wird festgelegt, welche Nachbarlegesteine Einfluss haben sollen auf den Folgezustand des Legesteins auf (i,j). Dabei soll dieser Folgezustand auch vom augenblicklichen Zustand des Legesteines abhängen. Man geht davon aus, dass zu einem bestimmten Taktzeitpunkt für sämtliche Legesteine überprüft wird, welche Folgezustände anzunehmen sind. Dann erfolgt getaktet für alle Steine der Übergang zu den neuen Zuständen. Diese getakteten Änderungen können beliebig wiederholt werden. Dabei können sich auf dem Spielbrett verschiedene Zustandsmuster für die Legesteine ergeben. Diese Muster werden wir untersuchen. Formaler - und etwas vereinfacht - kann man einen zellulären Automaten in folgender Weise beschreiben: Jede Zelle (i,j) ist ein Automat mit Zuständen aus einer Menge Z. (Bei uns i.A. Z={0,1} ). Eine Umgebung von (i,j) - U(i,j) - ist eine Teilmenge von {(i-1,j), (i+1,j), (x-1,y-1), (i,y-1), (i+1,y-1), (x-1,j+1), (i,j+1), (i+1,j+1)}. Aus den z-Werten der Umgebung und dem z-Wert für (i,j) wird mit einer Funktion f der Folgezustandswert z=f(i,j) für (i,j) errechnet.

Definition eines zellulären Automaten in einem gegebenen Zellenfeld

Ein zellulärer Automat ist ein Tripel {Z,U,f}, Z ist eine Menge von Zuständen für die Zellen, U ist eine Umgebung, die verschiebungsinvariant für die Zelle (i,j) erklärt ist, Auf den z-Werten der Zellen der Umgebung U und dem z-Wert von (i,j) ist eine Funktion f mit Werten aus Z erklärt. f(i,j)=z ist der Folgezustand der Zelle (i,j). Die Anwendung der Funktion f erfolgt taktweise auf alle Zellen des Feldes. Wendet man das Mealy-Modell auf zelluläre Automaten an, so kann jede Zelle als ein Automat angesehen werden, dessen Eingaben die Funktionswerte von f(i,j) und dessen Zustände (identifiziert mit Ausgaben) zur Berechnung der Folgezustände von Nachbarzellen genutzt werden. Für das obige Beispiel hat der Zellautomat (i,j) dann die folgende Automatentafel Die Verbindung des Zellautomaten (i,j) mit seinen Nachbarzellen: Man sieht, dass die Behandlung von solchen Automatennetzen mithilfe von Mealymodellen unübersichtlich ist. Deshalb wird der zelluläre Automat als Einheit nach der obigen Definition behandelt.

Zur Themenwahl