Tupel A = (Z, X, S0, F, δ) der im folgenden beschriebenen Art. Hierbei sind Z und X endliche Mengen. Z ist die Menge der Zustände und X die Menge der Eingabesymbole. S0 ⊆ Z ist die Menge der Anfangszustände des endlichen Akzeptors. F ⊆ Z die Menge der Endzustände. \begin{eqnarray}\delta :Z\times X\to {\mathfrak{P}}(Z)\end{eqnarray} ist eine Abbildung, die angesetzt auf einen Zustand s ∈ Z und ein Eingabesymbol x ∈ X angibt, in welche Zustände der sich im Zustand s befindliche endliche Akzeptor bei Eingabe von x übergehen kann.
Die von einem endlichen Akzeptor erkannte (akzeptierte) Sprache ist die Menge L(A) der Folgen von Eingabesymbolen, die den endlichen Akzeptor ausgehend von einem Anfangszustand in einen Endzustand überführen.
Die Sprache L(A) ist formal definiert durch \begin{eqnarray}L(A):=\{w\in {X}^{* }:\exists {s}_{0}\in {S}_{0}:F\cap {\delta }^{* }({s}_{0},w)\ne \varnothing \}\end{eqnarray} mit \begin{eqnarray}{\delta }^{* }(s,{x}_{1}\ldots {x}_{k})=\delta ({\delta }^{* }(s,{x}_{1}\ldots {x}_{k-1}),{x}_{k})\end{eqnarray} und δ*(s, x1) = δ(s, x1) für alle x1, …, xk ∈ X. Wie bei endlichen Automaten unterscheidet man auch bei endlichen Akzeptoren zwischen nichtdeterministischen und deterministischen endlichen Akzeptoren.
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.