- Rechnermodell
-
Ein Automat oder eine abstrakte Maschine ist in der Informatik das Modell eines digitalen, zeitdiskreten Rechners. Ob es möglich oder sinnvoll ist, eine solche Maschine tatsächlich zu bauen, ist dabei zunächst unerheblich. Die Vereinfachung der Fähigkeiten erlaubt es, das Verhalten eines Automaten leichter zu verstehen und zu vergleichen – darauf kommt es an.
Der Automatenbegriff spielt eine zentrale Rolle in der Theoretischen Informatik. In der Berechenbarkeitstheorie und in der Komplexitätstheorie etwa stellen die Automaten den zugrunde liegenden Berechnungsbegriff. Automaten spielen auch in der Praktischen Informatik eine entscheidende Rolle, zum Beispiel im Compilerbau. In der Digitaltechnik werden Automaten zur Steuerung in digitalen und hybriden Systemen eingesetzt. Solche Steuerungsautomaten haben Anwendungen unter anderem in der Rechnerarchitektur, in Rechnernetzen und in Reaktiven Systemen.
Inhaltsverzeichnis
Verhalten eines Automaten
Das grundsätzliche Verhalten eines Automaten ist immer gleich: Dem Automaten wird von außen eine Eingabe als Folge von Zeichen vorgelegt. Der Automat hat einen Zustand. Jedes Mal, wenn ein Eingabezeichen eintrifft, kann sich abhängig vom Eingabezeichen und dem gegenwärtigen Zustand ein neuer Zustand, der Folgezustand, einstellen (Zustandsübergang oder Transition). Man kann die Menge der möglichen Zustandsübergänge, die das Verhalten des Automaten definiert, als das Programm des Automaten verstehen.
Deterministische und nichtdeterministische Automaten
Wenn der Folgezustand durch den gegenwärtigen Zustand und das Eingabezeichen immer eindeutig gegeben ist, dann spricht man von einem deterministischen Automaten. Allgemein aber kann man auch einen Spielraum (Freiheitsgrade) für die Zustandsübergänge zulassen. Der Automat darf dann auf dasselbe Paar von Zustand und Eingabezeichen unter mehreren möglichen Kandidaten einen Folgezustand willkürlich wählen. Dann spricht man von einem nichtdeterministischen Automaten. Der Nichtdeterminismus ist dann willkommen, wenn man das Verhalten der Umgebung modellieren möchte, das man nicht völlig genau kennt (don't know), oder wenn man Möglichkeiten für verschiedene Implementierungen offenlassen möchte (don't care).
Meist lässt man zusätzlich zu nichtdeterministischen Zustandsübergängen noch spontane Zustandsübergänge zu, das sind solche, die ohne Eingabezeichen stattfinden (ε-Übergänge).
Automaten mit und ohne Ausgabe
Automaten, die nur ihre Zustandsübergänge abwickeln, nennt man auch Transitionssysteme.
Daneben gibt es auch Automaten, die eine gewisse Teilmenge ihrer Zustände als Endzustände auszeichnen. Wenn ein Eingabewort den Automaten von einem ausgezeichneten Zustand, dem Startzustand, in einen der Endzustände führt, dann sagt man, der Automat akzeptiert das Eingabewort. Einen solchen Automaten nennt man deswegen einen Akzeptor. Ein Akzeptor eignet sich dazu, eine Formale Sprache zu definieren, nämlich die Menge aller endlichen Wörter, die der Automat akzeptiert.
Schließlich gibt es noch Automaten mit Ausgabe oder Transduktoren. Sie ordnen entweder jedem Zustand (Moore-Automaten) oder jedem Paar aus Zustand und Eingabezeichen (Mealy-Automaten) ein Ausgabezeichen zu. Auf diese Weise bildet ein Automat eine Verarbeitungseinheit.
Klassen von Automaten
Schlagen Sie auch in anderen Wörterbüchern nach:
Von neumann rechnermodell — John von Neumann Die von Neumann Architektur ist ein Referenzmodell für Computer, wonach ein gemeinsamer Speicher sowohl Computerprogrammbefehle als auch Daten hält. Von Neumann Systeme gehören nach der Flynnschen Klassifikation zur Klasse der… … Deutsch Wikipedia
Church'sche These — Die Church Turing These (benannt nach Alonzo Church und Alan Turing, auch Churchsche These genannt) trifft Aussagen über die Fähigkeiten einer Rechenmaschine. Sie lautet: Die Klasse der Turing berechenbaren Funktionen ist genau die Klasse der… … Deutsch Wikipedia
Churchsche These — Die Church Turing These (benannt nach Alonzo Church und Alan Turing, auch Churchsche These genannt) trifft Aussagen über die Fähigkeiten einer Rechenmaschine. Sie lautet: Die Klasse der Turing berechenbaren Funktionen ist genau die Klasse der… … Deutsch Wikipedia
These von Church — Die Church Turing These (benannt nach Alonzo Church und Alan Turing, auch Churchsche These genannt) trifft Aussagen über die Fähigkeiten einer Rechenmaschine. Sie lautet: Die Klasse der Turing berechenbaren Funktionen ist genau die Klasse der… … Deutsch Wikipedia
Church-Turing-These — Die Church Turing These (benannt nach Alonzo Church und Alan Turing, auch Churchsche These genannt) trifft Aussagen über die Fähigkeiten einer Rechenmaschine. Sie lautet: Die Klasse der Turing berechenbaren Funktionen ist genau die Klasse der… … Deutsch Wikipedia
Random Access Machine — Die Registermaschine (auch RAM für engl. random access machine) ist ein Rechnermodell der theoretischen Informatik, das einem realen Rechner (PC) sehr ähnlich ist. Das Modell geht auf eine Arbeit von John C. Shepherdson und Howard E. Sturgis aus… … Deutsch Wikipedia
APM — Die Abkürzung APM steht für: Active Portfolio Management, Investmentkurs an der Europa Universität Viadrina Advanced Power Management, Energieverwaltungsmethode in Computern Aktionen pro Minute, Maßeinheit beim Micromanagement (Computerspiel)… … Deutsch Wikipedia
Apm — Die Abkürzung APM steht für: Active Portfolio Management, Investmentkurs an der Europa Universität Viadrina Advanced Power Management, Energieverwaltungsmethode in Computern Aktionen pro Minute, Maßeinheit beim Micromanagement (Computerspiel)… … Deutsch Wikipedia
Apple Macintosh Plus — Der Macintosh Plus war ein Rechnermodell der Firma Apple. Er wurde im Jahre 1986 eingeführt und war bis 1990 im Programm. Der Macintosh Plus hatte als Prozessor einen Motorola 68000 mit 8 MHz Taktfrequenz und basierte auf dem Gehäuse des… … Deutsch Wikipedia
Computer-Algebra — Die Computeralgebra ist das Teilgebiet der Mathematik, das sich mit der symbolischen Manipulation algebraischer Ausdrücke beschäftigt. Inhaltsverzeichnis 1 Zweck 2 Effiziente exakte Arithmetik mit ganzen Zahlen 3 Effiziente exakte Arithmetik mit… … Deutsch Wikipedia