Mealy-Automat, ein im folgenden näher definiertes Tupel A = (Z, X, Y, S₀, δ). 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. S₀ ⊆ Z 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 s ∈ Z und ein Eingabesymbol x ∈ X 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 |S₀| > 1, oder sind mehrere Übergänge für einen Zustand s ∈ Z und ein Eingabesymbol x ∈ X möglich, d. h. gilt |δ(s, x)| > 1 so spricht man von einem nichtdeterministischen endlichen Automaten.

Ist |S₀| = 1 und |δ(s, x)| = 1 für alle s ∈ Z und x ∈ X, 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, S₀, δ, λ), wobei δ : Z × X → Z die Übergangsfunktion und λ : Z × X → Y die Ausgabefunktion des endlichen Automaten darstellt.

Gilt für alle Zustände s und alle Eingabesymbole x₁, x₂ ∈ X, daß aus (t₁, y₁) ∈ δ(s, x₁) und (t₂, y₂) ∈ δ(s, x₂) schon y₁ = y₂ folgt, d.h. ist das auszugebende Symbol nur abhängig von dem aktuellen Zustand des endlichen Automaten, so spricht man von einem Moore-Automaten.