Benutzer:Mario~dewiki/neuer endlicher automat

Endliche Automaten sind mathematische Modelle von sehr einfachen Rechenmaschinen, die besonders in der theoretischen Informatik, insbesondere bei der Berechenbarkeitstheorie und dem Compilerbau Anwendung finden.

Definition

Ein endlicher Automat ist ein 5-Tupel:

$M=(\Sigma ,Z,Z_{0},\delta ,Z_{E})$

Dabei sind die Elemente wie folgt definiert.

$\Sigma$ - Ist eine endliche Menge.

$Z$ - Ist eine zu $\Sigma$ disjunkte endliche Menge.

$Z_{0}$ - Ist eine Element von $Z\qquad \qquad Z_{0}\in Z$

$\delta$ - Eine Funktion $\Sigma \times Z\rightarrow Z$ (total)

$Z_{E}$ - Ist eine Teilmenge$Z\qquad \qquad Z_{E}\in Z$

Die Semantik der einzelnen Elemente ist die folgende:

$\Sigma$ - Ist das Eingabealphabet

$Z$ - Ist die Zustandsmenge

$Z_{0}$ - Ist der Startzustand

$\delta$ - Ist die Überführungsfunktion, sie ist gewöhnlich total, d.h. jedes Element der Ausgangsmenge $\Sigma$ hat ein Bild.

$Z_{E}$ - Sind die akzeptierende Zustände.

Beschreibung

Mit Hilfe eines endlichen Automaten kann ich die Gültigkeit eines Eingabewortes überprüfen. D.h. ich kann überprüfen ob ein gegebenes Wort in einer Sprache ist oder nicht. Erreicht wird dies durch den Automaten, indem er im Startzustand beginnt die einzelnen Buchstaben des Wortes einzulesen und bei jedem Buchstaben den Zustand wechselt (er kann auch im Zustand verbleiben). Ist das Ende des Wortes erreicht, entscheidet die Gültigkeit des Wortes am letzten Zustand. Ist der Zustand in der Menge $Z_{E}$ wird das Wort akzeptiert und gehört somit zur entsprechenden Sprache, andernfalls ist das Wort ungültig.

Beispiel

Es sei folgender Automat gegeben:

$M=({a,b,c},{X,Y,Z},\delta ,Z)$