Wikipedia · einfach zusammengefasst · Stand
Mealy-Automat
Ein Mealy-Automat ist in der theoretischen Informatik ein deterministischer endlicher Automat, dessen Ausgabe von seinem Zustand und seiner Eingabe abhängt; …
Inhalt3 Abschnitte
Grundidee
Ein Mealy-Automat ist ein deterministischer endlicher Automat der theoretischen Informatik. Seine Ausgabe hängt sowohl vom aktuellen Zustand als auch von der Eingabe ab. Im Zustandsdiagramm wird deshalb jeder Kante ein Ausgabewert zugeordnet.
Bestandteile eines Mealy-Automaten
Ein Mealy-Automat ist ein 7-Tupel \mathcal{A}=(Q,\Sigma,\Omega,\delta,\lambda,q_0,F):
- Q ist eine endliche Menge von Zuständen, also |Q|<\infty; dafür wird auch Z verwendet.
- \Sigma ist das endliche Eingabealphabet und \Omega das endliche Ausgabealphabet.
- \delta\colon Q\times\Sigma\to Q ist die Übergangsfunktion. Sie legt fest, in welchen Zustand der Automat bei einer Eingabe wechselt.
- \lambda\colon Q\times\Sigma\to\Omega ist die Ausgabefunktion. Sie bestimmt die Ausgabe zu Zustand und Eingabe.
- Beide Funktionen können als \zeta\colon Q\times\Sigma\to\Omega\times Q zusammengefasst werden.
- q_0\in Q ist der Startzustand; auch z_0 oder S_0 sind gebräuchlich. Im Diagramm wird er doppelt umrandet oder mit einem Doppelpfeil markiert.
- F\subseteq Q ist die endliche Menge akzeptierender Zustände, also die Endzustandsmenge.
Ist die vom Automaten akzeptierte reguläre Sprache nicht wichtig, kann F weggelassen werden; dann ist der Automat als 6-Tupel definiert.
Beispiel und Vergleich zum Moore-Automaten
Ein Beispielautomat gibt die Eingabe um ein Zeichen verzögert aus: Zur Eingabe x_0x_1...x_n erzeugt er 0x_0x_1...x_{n-1}. Eine Kantenbeschriftung 0/1 bedeutet: Bei Eingabe einer Null wechselt der Automat den Zustand und gibt zusätzlich eine Eins aus.
Bei einem Moore-Automaten hängt die Ausgabe dagegen nicht von der Eingabe ab. Mealy- und Moore-Automaten können ineinander umgewandelt werden. Für die Umwandlung eines Mealy- in einen Moore-Automaten wird zunächst die Ausgabe jeder Kante in den Zustand übertragen, auf dem die Kante endet. Dann werden Zustände aufgespalten, sodass jedem Zustand höchstens ein Ausgabewert zugeordnet ist, und eingehende Kanten werden passend umgehängt. Schließlich werden die ausgehenden Kanten der ursprünglichen Zustände kopiert und an die neuen Zustände angehängt. Der so konstruierte Moore-Automat hat eine zur Ausgabe des ursprünglichen Mealy-Automaten äquivalente Ausgabe.
