Direkt zum Inhalt

Lexikon der Mathematik: endlicher Automat

Mealy-Automat, ein im folgenden näher definiertes Tupel A = (Z, X, Y, S0, δ). Hierbei sind Z, X und Y endliche Mengen. Z ist die Menge der Zustände, X die Menge der Eingabesymbole und Y die Menge der Ausgabesymbole. S0Z ist die Menge der Anfangszustände des endlichen Automaten. \begin{eqnarray}\delta :Z\times X\to {\mathfrak{P}}(Z\times Y)\end{eqnarray} ist eine Abbildung, die angesetzt auf einen Zustand sZ und ein Eingabesymbol xX die Menge der möglichen Übergänge (t, y) des endlichen Automaten angibt.

Ist (t, y) ∈ δ(s, x), so kann der sich im Zustand s befindliche endliche Automat bei Eingabe des Symbols x in den Zustand t übergehen und bei diesem Übergang das Symbol y ausgeben.

Ist |S0| > 1, oder sind mehrere Übergänge für einen Zustand sZ und ein Eingabesymbol xX möglich, d. h. gilt |δ(s, x)| > 1 so spricht man von einem nichtdeterministischen endlichen Automaten.

Ist |S0| = 1 und |δ(s, x)| = 1 für alle sZ und xX, so spricht man von einem deterministischen endlichen Automaten.

In diesem Fall beschreibt man in der Regel den endlichen Automaten durch ein 6-Tupel (Z, X, Y, S0, δ, λ), wobei δ : Z × XZ die Übergangsfunktion und λ : Z × XY die Ausgabefunktion des endlichen Automaten darstellt.

Gilt für alle Zustände s und alle Eingabesymbole x1, x2X, daß aus (t1, y1) ∈ δ(s, x1) und (t2, y2) ∈ δ(s, x2) schon y1 = y2 folgt, d.h. ist das auszugebende Symbol nur abhängig von dem aktuellen Zustand des endlichen Automaten, so spricht man von einem Moore-Automaten.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos