Endlicher Automat - Versionsgeschichte

Thomas: /* Beispiel */

2025-08-29T12:54:45Z

Beispiel

← Nächstältere Version		Version vom 29. August 2025, 14:54 Uhr
Zeile 138:		Zeile 138:
	=== Beispiel ===		=== Beispiel ===

	Das folgende Diagramm beschreibt einen NEA mit ε-Übergängen. Dieser Automat lässt sich als 5-Tupel beschreiben:		Das folgende Diagramm beschreibt einen NEA mit ε-Übergängen. Dieser Automat lässt sich als 5-Tupel beschreiben (Quelle: https://hwlang.de/theor/index.htm):
			[[Datei:ENEA.png\|mini]]

	Q: 0-7		Q: 0-7

Thomas: /* Potenzmengenkonstruktion */

2025-08-29T12:52:22Z

Potenzmengenkonstruktion

@@ Zeile 122: / Zeile 122: @@
 [[Datei:NEA Beispiel.png|mini]]
 [[Kategorie:Automaten]]
 [[Kategorie:AHR_I_Informatik_LK]]

Thomas: /* Potenzmengenkonstruktion */

2025-08-29T12:46:20Z

Potenzmengenkonstruktion

← Nächstältere Version		Version vom 29. August 2025, 14:46 Uhr
Zeile 107:		Zeile 107:

	Wir bertachten folgenden NEA als 5-Tupel (Quelle: https://de.wikipedia.org/wiki/Potenzmengenkonstruktion#Beispiele)		Wir bertachten folgenden NEA als 5-Tupel (Quelle: https://de.wikipedia.org/wiki/Potenzmengenkonstruktion#Beispiele)
			[[Datei:5Tupel.png\|mini]]

	Q: S0,S1,S2,S3		Q: S0,S1,S2,S3

Thomas: /* Übergangsfunktion */

2025-08-29T12:44:29Z

Übergangsfunktion

← Nächstältere Version		Version vom 29. August 2025, 14:44 Uhr
Zeile 54:		Zeile 54:

	Beispiel Übergangsfunktion für den Bonbonautomat:		Beispiel Übergangsfunktion für den Bonbonautomat:
			[[Datei:Tabelle Übergangsfunktion.png\|mini]]

	== DEA - Deterministischer endlicher Automat ==		== DEA - Deterministischer endlicher Automat ==

Thomas am 29. August 2025 um 12:42 Uhr

2025-08-29T12:42:11Z

@@ Zeile 39: / Zeile 39: @@
 Bonbonautomat als Mealy Automat: A = {Q,s,∑,Ω, δ, λ}
-=== Grafische Darstellung ===
+[[Datei:Grafische Darstellung Mealy-Automat Bonbons.jpg|mini]]
 [[Kategorie:Automaten]]
 [[Kategorie:AHR_I_Informatik_LK]]

Thomas am 29. August 2025 um 12:27 Uhr

2025-08-29T12:27:34Z

← Nächstältere Version		Version vom 29. August 2025, 14:27 Uhr
Zeile 1:		Zeile 1:
	== Einführung ==		== Einführung ==
	Ein endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat; englisch finite state machine, FSM) ist ein mathematisches Modell eines Systems mit diskreten Ein- und Ausgaben. Diskret bedeutet, dass zu jedem Zeitpunkt nur eine Eingabe und eine Ausgabe verarbeitet wird. Es gibt eine endliche Anzahl ein Ein- und Ausgaben. Das durch den Automaten beschriebene System befindet sich in einer endlichen Anzahl von Zuständen. Das Verhalten des Systems wird durch Zustände, Zustandsübergängen und Aktionen beschrieben.		Ein endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat; englisch finite state machine, FSM) ist ein mathematisches Modell eines Systems mit diskreten Ein- und Ausgaben. Diskret bedeutet, dass zu jedem Zeitpunkt nur eine Eingabe und eine Ausgabe verarbeitet wird. Es gibt eine endliche Anzahl ein Ein- und Ausgaben. Das durch den Automaten beschriebene System befindet sich in einer endlichen Anzahl von Zuständen. Das Verhalten des Systems wird durch Zustände, Zustandsübergängen und Aktionen beschrieben.

			Automaten lassen sich unteranderem durch ein [[Zustandsdiagramm\|UML Zustandsdiagramm]] darstellen.

	== Motivation ==		== Motivation ==

Flbkwikiadmin am 27. August 2025 um 08:17 Uhr

2025-08-27T08:17:38Z

← Nächstältere Version		Version vom 27. August 2025, 10:17 Uhr
Zeile 40:		Zeile 40:

	[[Kategorie:Automaten]]		[[Kategorie:Automaten]]
			[[Kategorie:AHR_I_Informatik_LK]]

Thomas: Thomas verschob die Seite EndlicherAutomat nach Endlicher Automat: Falsch geschriebener Name: Felix kann sich das einfach nicht merken

2025-08-27T08:10:52Z

Thomas verschob die Seite EndlicherAutomat nach Endlicher Automat: Falsch geschriebener Name: Felix kann sich das einfach nicht merken

← Nächstältere Version	Version vom 27. August 2025, 10:10 Uhr
(kein Unterschied)

Thomas am 27. August 2025 um 07:52 Uhr

2025-08-27T07:52:26Z

← Nächstältere Version		Version vom 27. August 2025, 09:52 Uhr
Zeile 38:		Zeile 38:

	=== Grafische Darstellung ===		=== Grafische Darstellung ===

			[[Kategorie:Automaten]]

Thomas: Die Seite wurde neu angelegt: „== Einführung == Ein endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat; englisch finite state machine, FSM) ist ein mathematisches Modell eines Systems mit diskreten Ein- und Ausgaben. Diskret bedeutet, dass zu jedem Zeitpunkt nur eine Eingabe und eine Ausgabe verarbeitet wird. Es gibt eine endliche Anzahl ein Ein- und Ausgaben. Das durch den Automaten beschriebene System befindet sich in einer endlichen Anzahl von Zuständen. Das Verhalten d…“

2025-08-27T07:49:00Z

Die Seite wurde neu angelegt: „== Einführung == Ein endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat; englisch finite state machine, FSM) ist ein mathematisches Modell eines Systems mit diskreten Ein- und Ausgaben. Diskret bedeutet, dass zu jedem Zeitpunkt nur eine Eingabe und eine Ausgabe verarbeitet wird. Es gibt eine endliche Anzahl ein Ein- und Ausgaben. Das durch den Automaten beschriebene System befindet sich in einer endlichen Anzahl von Zuständen. Das Verhalten d…“

Neue Seite

== Einführung ==
Ein endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat; englisch finite state machine, FSM) ist ein mathematisches Modell eines Systems mit diskreten Ein- und Ausgaben. Diskret bedeutet, dass zu jedem Zeitpunkt nur eine Eingabe und eine Ausgabe verarbeitet wird. Es gibt eine endliche Anzahl ein Ein- und Ausgaben. Das durch den Automaten beschriebene System befindet sich in einer endlichen Anzahl von Zuständen. Das Verhalten des Systems wird durch Zustände, Zustandsübergängen und Aktionen beschrieben.

== Motivation ==
Computer, andere Maschinen oder Programme erscheinen im Alltag oft als eine Black Box, egal ob sie triviale oder schwierige Probleme lösen. Sie reagieren auf Eingaben, verarbeiten Informationen, ohne dass wir sehen, wie, und präsentieren eine Antwort bzw. eine Lösung. Manchmal scheinen Sie sogar ‚intelligenter‘ als Menschen zu sein, wenn sie gegen Schachweltmeister gewinnen, die 2,7 Billionen Nachkommastellen von n berechnen, einem sagen, was man als Nächstes kaufen möchte oder man mit einem Computer spricht, ohne es zu bemerken.

Doch das Verarbeiten der Eingaben ist weder Zauberei, noch (zumindest bis heute) intelligentes Vorgehen. Es sind Programme, die das Verhalten der Maschine bestimmen, und diese Maschinen lassen sich sogar durch einfach strukturierte Modelle wie den endlichen Automaten beschreiben. Die Einfachheit des Modells sollte aber nicht über deren Mächtigkeit hinwegtäuschen.
Das Automatenmodell dient zum Beispiel der Zellforschung als probates Mittel, um das Verhalten von Zellen zu beschreiben, und auch die Hirnforschung greift bei der Beschreibung des Gehirns durch neurale Netze darauf zurück. Automaten findet man außerdem in zahlreichen Alltagssituationen vor: Fahrstühle, Ampel Waschmaschinen, Getränke, Fahrkarten- und Geldautomaten sind nur einige der vielen Maschinen, die von einem endlichen Automaten gesteuert werden.

Diese Automaten werden als endlich bezeichnet, weil die Menge der Eingaben, der Ausgaben und der Zustände, die sie durchlaufen, endlich sind. Folgt ein Automat folgender formalen Beschreibung, dann bezeichnet man diesen als Mealy-Automat.

== Mealy-Automat ==
=== Definition ===
Für die Formalisierung des Automaten führt man zunächst die Ein- und Ausgabe ein. Sie werden als Eingabe und Ausgabealphabet bezeichnet. Der Begriff erklärt sich aus der Tatsache, dass Computer in der Regel Texte, also Zeichenfolgen eines Alphabets verarbeiten. Auch die Verarbeitung in einem Computer kann, da sie durch 0 und 1 repräsentiert wird, als die Verarbeitung von Texten angesehen werden.

Des Weiteren muss der Automat durch eine Zustandsmenge speichern, welche Eingaben bisher getätigt wurden. Die Zustände werden oft mit q0 ... qn bezeichnet. Mithilfe der Übergangsfunktion wird die zeitliche Abfolge der Ereignisse festgelegt. Die Übergangsfunktion gibt an, was welche Eingabe in jedem Zustand bewirkt. Neben der Übergangsfunktion gibt es noch die Ausgabefunktion, die angibt, welche Ausgabe durch die jeweilige Eingabe in einem Zustand ausgelöst wird. Die Übergangs- und Ausgabefunktionen werden tabellarisch oder grafisch als sogenannter Transitionsgraph oder Übergangsgraph dargestellt. Ein solcher Automat wird in der lnformatik als Mealy-Automat bezeichnet.

Formal definiert man einen Mealy-Automat als 6-Tupel A = {Q,s,∑,Ω, δ, λ}

Q ist eine nicht leere, endliche Menge von Zuständen

s∈Q ist der Startzustand

∑ ist ein nicht leeres, endliches Eingabealphabet

Ω ist ein nicht leeres, endliches Ausgabealphabet

δ:Qx∑ ->Q ist die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen einen Nachfolgezustand zuordnet.

λ:Qx∑->Ω ist die Ausgabefunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen eine Ausgabe zuordnet.

=== Beispiel ===
Die Funktionsweise eines endlichen Automaten lässt sich leicht an einer einfachen Maschine wie einem Bonbonautomaten erläutern. Der Bonbonautomat lässt sich in seiner Funktionsweise wie folgt beschreiben. Die Eingabe besteht aus der richtigen Münze und dem Drehen des Hebels. Die Verarbeitung erfolgt im Inneren des Automaten und führt zur Ausgabe, dem Bonbon im Ausgabefach.

Die Eingabemöglichkeiten des Automaten sind begrenzt, es kommt jedoch auf die korrekte Reihenfolge an. Dreht man zuerst den Hebel und wirft dann die korrekte Münze ein, so erhält man nicht die gewünschte Ausgabe. Dazu wäre ein weiteres Drehen des Hebels erforderlich.

Bonbonautomat als Mealy Automat: A = {Q,s,∑,Ω, δ, λ}

=== Grafische Darstellung ===