Direkt zum Inhalt

Lexikon der Mathematik: endlicher Akzeptor

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. S0Z ist die Menge der Anfangszustände des endlichen Akzeptors. FZ 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 sZ und ein Eingabesymbol xX 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, …, xkX. Wie bei endlichen Automaten unterscheidet man auch bei endlichen Akzeptoren zwischen nichtdeterministischen und deterministischen endlichen Akzeptoren.

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