imported>Geist, der stets verneint: Änderungen von 2A01:599:209:ACC4:F4EB:974A:919F:BBD2 (Diskussion) auf die letzte Version von Gustav von Aschenbach zurückgesetzt

2024-01-25T17:47:57Z

Änderungen von 2A01:599:209:ACC4:F4EB:974A:919F:BBD2 (Diskussion) auf die letzte Version von Gustav von Aschenbach zurückgesetzt

Neue Seite

Ein '''Automat''' oder eine '''abstrakte Maschine''' ist in der [[Informatik]], speziell in der [[Automatentheorie]], das [[Modell]] eines [[Digitalsignal|digitalen]], [[Diskretheit|zeitdiskreten]] [[Computer|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.

Der Automatenbegriff spielt eine zentrale Rolle in der [[Theoretische Informatik|theoretischen Informatik]]. In der [[Berechenbarkeitstheorie]] und in der [[Komplexitätstheorie]] etwa stellen die Automaten den zugrunde liegenden Berechnungsbegriff. Automaten spielen auch in der [[Praktische Informatik|praktischen Informatik]] eine entscheidende Rolle, zum Beispiel im [[Compilerbau]].
In der [[Digitaltechnik]] werden Automaten zur [[Steuerungstechnik|Steuerung]] in ''digitalen'' und ''[[hybrid]]en Systemen'' eingesetzt. Solche Steuerungsautomaten haben Anwendungen unter anderem in der [[Rechnerarchitektur]], in [[Rechnernetz]]en und in [[Reaktives System|Reaktiven Systemen]].

== 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 befindet sich in einem bestimmten 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 [[Computerprogramm|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 [[Determinismus (Algorithmus)|deterministischen]] Automaten. Allgemein aber kann man auch einen Spielraum ([[Freiheitsgrad]]e) 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 [[Nichtdeterminismus|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 [[Transitionssystem]]e.

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 (Informatik)|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, sogenannte [[Transduktor (Informatik)|Transduktoren]]. Sie ordnen entweder jedem Zustand ([[Moore-Automat]]en) oder jedem Paar aus Zustand und Eingabezeichen ([[Mealy-Automat]]en) ein Ausgabezeichen zu. Auf diese Weise bildet ein Automat eine Verarbeitungseinheit.

== Klassen von Automaten ==

[[Datei:Turingmaschine.svg|mini|[[Turingmaschine]]]]
[[Datei:Kellerautomat.svg|mini|[[Kellerautomat]]]]
[[Datei:Nichtdeterministischer endlicher Automat 2.svg|mini|[[Endlicher Automat]]]]
[[Datei:Registermaschine.svg|mini|[[Registermaschine]]]]

Nach den Mitteln, die ein Automat zur Verfügung hat, kann man die Automaten in Klassen einteilen.
Statt Klasse von Automaten sagt man auch '''Automatenmodell'''.
Den Akzeptoren der jeweiligen Klasse kann man ihre akzeptierte Sprache zuordnen. Es stellt sich heraus, dass jeder Klasse von Automaten auf diese Weise eine Klasse Formaler Sprachen entspricht.
Bekannte Klassen von Automaten sind (jeweils mit Abkürzungen für die deterministische und die nichtdeterministische Variante):

; [[Turingmaschine]]n (DTM/NTM)
: Eine Turingmaschine hat neben dem inneren Zustand auch Zugriff auf ein unendliches Band, auf das ein beweglicher Schreib-/Lesekopf Zeichen schreiben und später lesen kann. Beide Klassen akzeptieren die Typ-0-Sprachen ([[Rekursiv aufzählbare Sprache]]). Durch die Turingmaschine wird außerdem der Begriff der [[Berechenbarkeit]] definiert. Siehe [[Churchsche These]].
; [[Linear beschränkter Automat|Linear beschränkte Automaten]] (DLBA/LBA)
: Die linear beschränkten Automaten unterscheiden sich von den Turingmaschinen nur dadurch, dass der zugängliche Teil des Bandes durch die Größe der Eingabe beschränkt ist. Nichtdeterministische LBA akzeptieren genau die Typ-1-Sprachen ([[Kontextsensitive Sprache|kontextsensitive Sprachen]]); die Frage, ob das auch auf deterministische LBA zutrifft, ist ein noch offenes Problem.
; [[Kellerautomat]]en (DPDA/PDA)
: Ein Kellerautomat hat neben einem von endlich vielen inneren Zuständen auch Zugriff zum Keller, einem [[Stapelspeicher|Stapel]], auf dem Zeichen zur späteren Verarbeitung zwischengespeichert werden können. Die PDAs akzeptieren die Typ-2-Sprachen ([[Kontextfreie Sprache]]n). Die DPDAs akzeptieren die [[Deterministisch kontextfreie Sprache|deterministisch kontextfreien Sprachen]].
; [[Endlicher Automat|Endliche Automaten]] (DFA/NFA)
: Ein endlicher Automat kennt nur endlich viele Zustände. Beide Klassen akzeptieren die Typ-3-Sprachen ([[Reguläre Sprache]]n).

Die Menge der Automaten stehen wie folgt mit den Mengen der [[Sprachklasse]]n und [[Formale Grammatik|Grammatiken]] in Beziehung (siehe auch [[Chomsky-Hierarchie]]):

{| class="wikitable" style="text-align:center"
|-
! Chomsky-Hierarchie
! Sprachklasse
|
! nicht deterministischer Automat
|
! deterministischer Automat
|-
| Typ-0-Grammatik
| [[Rekursiv aufzählbare Sprache|<math>\mathcal{\color{blue}RE}</math>]]
|style="font-size:larger"| <math>=</math>
| [[Nichtdeterministische Turingmaschine|<math>\mathcal{\color{blue}NTM}</math>]]
|style="font-size:larger"| <math>=</math>
| [[Turingmaschine|<math>\mathcal{\color{blue}DTM}</math>]]
|-
| Typ-1-Grammatik
| [[Kontextsensitive Sprache|<math>\mathcal{\color{blue}CS}</math>]]
|style="font-size:larger"| <math>=</math>
| [[Linear beschränkter Automat|<math>\mathcal{\color{blue}LBA}</math>]]
| <math>\supseteq</math>
| <math>\mathcal{DLBA}</math>
|-
| Typ-2-Grammatik
| [[Kontextfreie Sprache|<math>\mathcal{\color{blue}CF}</math>]]
|style="font-size:larger"| <math>=</math>
| [[Kellerautomat|<math>\mathcal{\color{blue}PDA}</math>]]
| <math>\varsupsetneq</math>
| <math>\mathcal{DPDA}</math>
|-
| Typ-3-Grammatik
| [[Reguläre Sprache|<math>\mathcal{\color{blue}REG}</math>]]
|style="font-size:larger"| <math>=</math>
| [[Nichtdeterministischer endlicher Automat|<math>\mathcal{\color{blue}NFA}</math>]]
|style="font-size:larger"| <math>=</math>
| [[Deterministischer endlicher Automat|<math>\mathcal{\color{blue}DFA}</math>]]
|}

Ob LBA ⊃ DLBA echt gilt, oder ob die DLBAs die gleiche Sprachklasse akzeptieren wie die LBAs, ist noch nicht bekannt.

Weitere Klassen von Automaten sind:
; [[Zweikellerautomat]]
: Beim Zweikellerautomat hat man im Unterschied zum Kellerautomaten zwei Keller zur Verfügung. Durch das Kellerpaar kann ein Turingband simuliert werden. Die Zweikellerautomaten sind also den Turingmaschinen gleichwertig. Syntaktische Beschränkungen dieses Modells führen zur Charakterisierung der Typ-1- und Typ-2-Sprachen.
; [[Registermaschine]]n
: Eine Registermaschine hat zusätzlich zum inneren Zustand eine Folge von Registern, das sind Speicherzellen für natürliche Zahlen, auf denen elementare Rechenoperationen ausgeführt werden können. Registermaschinen sind genau so mächtig wie Turingmaschinen.

== Erweiterte Automatenbegriffe ==

Nichtdeterministische Automaten dürfen nicht verwechselt werden mit [[Stochastischer Automat|Stochastischen Automaten]]. Letztere ordnen den Zustandsübergängen Wahrscheinlichkeiten zu, während erstere nur über Möglichkeiten reden. Für Wahrscheinlichkeitsaussagen sind nichtdeterministische Automaten daher nicht geeignet.

Daneben gibt es weitere Automatentypen, die sich nicht am sequentiellen Einlesen einer Eingabe orientieren. Einige der bekannteren Automaten sind:
* Varianten der [[Turingmaschine]] mit zweidimensionalem Band oder mit mehreren Bändern
* [[Zellulärer Automat|Zelluläre Automaten]]
* [[ω-Automat]]en für unendliche Eingaben
* [[Künstliches neuronales Netz|Neuronale Netze]]
* [[Petri-Netz]]e
* [[Algebraische Rechenmodelle]]

== Anwendungen ==

Von praktischer Relevanz für die [[Programmierung]] sind vor allem Endliche Automaten und Kellerautomaten: sie bieten eine einfache Struktur, mit der sich viele komplexe Probleme übersichtlich lösen lassen. Im Compilerbau werden sie beispielsweise zur [[Implementierung]] von [[Parser]]n eingesetzt, die Umsetzungen von [[Netzwerkprotokoll]]en benutzen häufig einen endlichen Automaten, um ihren aktuellen Zustand zu [[Modellierung|modellieren]]. Auch die Navigationsmöglichkeiten in einem [[Assistent (Datenverarbeitung)|Wizard]] lassen sich sehr gut als endlicher Automat ausdrücken, und das [[Workflow-Management]] benutzt diese Konzepte zur Modellierung von Arbeitsabläufen.

Auch bei der Realisierung sequenzieller [[Hardware]] wird das Modell des Endlichen Automaten genutzt, dort meist als [[Finite State Machine]] (FSM) bezeichnet.

[[Kategorie:Automatentheorie|!]]

Automat (Informatik) - Versionsgeschichte

imported>Geist, der stets verneint: Änderungen von 2A01:599:209:ACC4:F4EB:974A:919F:BBD2 (Diskussion) auf die letzte Version von Gustav von Aschenbach zurückgesetzt