Programme, Algorithmen und Automaten

Begriff: „Algorithmus“

Allgemein gesagt, gibt ein Algorithmus eine Vorgehensweise vor, um ein Problem zu lösen. Anhand dieses Lösungsplans werden in Einzelschritten Eingabedaten in Ausgabedaten umgewandelt.

Eigenschaften von Algorithmen

Algorithmen besitzen die folgenden Charakteristiken:

Eindeutigkeit: Ein Algorithmus darf keine widersprüchliche Beschreibung haben. Sie muss eindeutig sein.
Ausführbarkeit: Jeder Einzelschritt muss ausführbar sein.
Finitheit (= Endlichkeit): Die Beschreibung des Algorithmus muss endlich sein.
Terminierung: Nach endlich vielen Schritten muss der Algorithmus enden und ein Ergebnis liefern.
Determiniertheit: Der Algorithmus muss bei gleichen Voraussetzungen stets das gleiche Ergebnis liefern.
Determinismus: Zu jedem Zeitpunkt der Ausführung besteht höchstens eine Möglichkeit der Fortsetzung. Jeder Folgeschritt ist also eindeutig.

Unterschied: Algorithmus und Programm

Ein Programm wird in einer bestimmten Programmiersprache geschrieben, wobei ein Algorithmus unabhängig von der Informatik ist, also auch von Menschen bearbeitet werden kann (die Idee steht im Vordergrund).

Was ist ein Automat?

Aus informatischer Sicht ist ein Automat eine abstrakte Maschine. Sie ist ein Modell eines Rechners oder anderen Maschinen. Die Automatentheorie hilft das Verhalten einer Maschine leichter zu verstehen und zu vergleichen. Außerdem kann man mit Automaten komplexe Systeme leichter und strukturierter entwickeln.

Automaten werden in Zustandsdiagrammen notiert.

Zustandsdiagramm: Beispiel

Zustandsdiagramm: Zeichen

Zeichen eines Zustandsdiagramms — Quelle

Arten von Automaten

Es gibt deterministische Automaten, bei denen der Folgezustand immer eindeutig aus dem gegenwärtigen Zustand abzuleiten ist.

Zudem gibt es nichtdeterministische Automaten, die ihren Folgezustand aus mehreren möglichen Kandidaten wählen.

Automat: mathematische Beschreibung

Automaten werden durch Tupel beschrieben. Ein Tupel ist eine endliche Liste von Objekten.

Mealy-Automat

Ein Mealy-Automat wird als 6-Tuple $(Q, s, \Sigma, \Omega, \delta, \lambda)$ beschrieben.

$Q$ : Eine nicht leere, endliche Menge von Zuständen => Zustandsmenge
$s \in Q$ : Startzustand
$\Sigma$ : Ein nicht leeres, endliches Eingabealphabet
$\Omega$ : Ein nicht leeres, endliches Ausgabealphabet
$\delta:Q \times \Sigma \rightarrow Q$ : Die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen einen Nachfolgezustand zuordnet.
$\lambda: Q \times \Sigma \rightarrow \Omega$ : Eine Ausgabefunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen eine Ausgabe zuordnet.

Deterministische endliche Automaten (DEA)

Die deterministischen endlichen Automaten entscheiden ob eine Eingabe über einem Eingabealphabet korrekt ist oder nicht. Die Ausgabe spielt hierbei keine Rolle, jedoch müssen Final– oder Endzustände $F$ , die nur bei korrekter Eingabe erreicht werden definiert sein.

Er wird als 5-Tupel $(Q, s, \Sigma, F, \delta)$ beschrieben.

$Q$ : Eine nicht leere, endliche Menge von Zuständen => Zustandsmenge
$s \in Q$ : Startzustand
$\Sigma$ : Ein nicht leeres, endliches Eingabealphabet
$F$ : Eine Menge der Akzeptierenden Endzustände, $F \subseteq Q$
$\delta:Q \times \Sigma \rightarrow Q$ : Die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen einen Nachfolgezustand zuordnet.

Nichtdeterministische endliche Automaten (NEA)

Bei nichtdeterministische endliche Automaten gibt es bei einer Eingabe mehrere mögliche Ausgangszustände. Der Automat testet alle möglichen Entscheidungen und akzeptiert ein Wort nur wenn es einen Weg zu einem akzeptierenden Endzustand $F$ gibt.

$Q$ : Eine nicht leere, endliche Menge von Zuständen => Zustandsmenge
$s \in Q$ : Startzustand
$\Sigma$ : Ein nicht leeres, endliches Eingabealphabet
$F$ : Eine Menge der Akzeptierenden Endzustände, $F \subseteq Q$
$\delta:Q \times \Sigma \rightarrow P(Q)$ : Die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen einen Nachfolgezustand zuordnet. $P(Q)$ beschreibt die Potenzmenge von $Q$ .

Beispiel: Viagra E-Mail-Filter

Viagra E-Mail-Filter Automat — Epsilon $\epsilon$ ist ein Teil von $\Sigma$ , der einen automatischen Übergang in einen nächsten Zustand beschreibt.

Jeder NEA lässt sich mithilfe einer Potenzmengenkonstruktion in einen deterministischen Automaten überführen (konvertieren).