Endlicher Automat: Unterschied zwischen den Versionen

← Zum vorherigen Versionsunterschied Zum nächsten Versionsunterschied →

VisuellWikitext

@@ Zeile 39: / Zeile 39: @@
 Bonbonautomat als Mealy Automat: A = {Q,s,∑,Ω, δ, λ}
-=== Grafische Darstellung ===
+[[Datei:Grafische Darstellung Mealy-Automat Bonbons.jpg|mini]]
+== Übergangsfunktion ==
+Die Übergangsfunktion δ:Qx∑ ->Q ordnet jeder Kombination aus einem Zustand (erste Spalte) und einem Eingabezeichen (erste Zeile) einen Nachfolgezustand (Matrix) zu. Dies lässt sich sehr gut tabellarisch darstellen:
+M: Münze einwerfen
+H: Hebel drehen
+B: Bonbon ausgeben
+N: Keine Ausgabe
+Gäbe es einen Endzustand, würde dieser in der Tabelle mit einem Stern kenntlich gemacht.
+Beispiel Übergangsfunktion für den Bonbonautomat:
+== DEA - Deterministischer endlicher Automat ==
+=== Definition ===
+Ein Automat heißt deterministisch, wenn für jeden seiner Zustände für jedes Eingabezeichen nur genau ein Folgezustand existiert. Das Verhalten des Automaten ist somit eindeutig bestimmt. Der deterministische endliche Automat ist genau wie der Mealy-Automat dadurch gekennzeichnet, dass er eine endliche Menge an Zuständen besitzt und die Übergänge von einem Zustand zum anderen deterministisch definiert sind, es also keine Wahlmöglichkeiten für den Zustandswechsel bei einer konkreten Eingabe gibt. Er besitzt jedoch kein Ausgabealphabet und keine Ausgabefunktion, dafür aber eine Menge an akzeptierenden Endzuständen.
+Bildlich kann man sich den DEA wie eine Blackbox vorstellen, die sich einem Zustand S befindent und eine Folge von Buchstaben aus ∑ liest. Der DEA geht die Buchstaben einzeln durch bis ein Wort entsteht und gemäß Zustandsübergangsfunktion einen Folgezustand erreicht wird, der einen definierten Endzustand für den DEA darstellt.
+Solche DEA können z. B. überprüfen, ob in einer Kaffeemaschine das Kaffeeersatzfach geleert werden muss. Dazu muss eine Spezifikation des Problems vorliegen, anhand derer sich das Problem als deterministischer Automat formalisieren lässt.
+Formal definiert man einen DEA als 5-Tupel  A = {Q,s,∑,F, δ}:
+Q ist eine nicht leere, endliche Menge von Zuständen
+s∈Q ist der Startzustand
+∑ ist ein nicht leeres, endliches Eingabealphabet
+F die Menge der zu akzeptierenden Endzustände, wobei F eine Teilmenge von von Q ist.
+δ:Qx∑ ->Q ist die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen einen Nachfolgezustand zuordnet.
+[[Datei:DEA Kaffeeautomat.jpg|mini]]
+Nichtdeterministischer endlicher Automat
+=== Definition ===
+Ein nichtdeterministischer endlicher Automat (NEA; englisch nondeterministic finite automaton, NFA) ist ein endlicher Automat, bei dem es für den Zustandsübergang mehrere gleichwertige Möglichkeiten gibt. Im Unterschied zum deterministischen endlichen Automaten sind die Möglichkeiten nicht eindeutig, dem Automaten ist also nicht vorgegeben, welchen Übergang er zu wählen hat.
+Formal kann ein NEA A als (5-Tupel ( Q , Σ , Δ , S , F) definiert werden. Hierbei gilt Folgendes:
+Q ist eine nicht leere, endliche Menge von Zuständen
+s∈Q ist der Startzustand
+∑ ist ein nicht leeres, endliches Eingabealphabet
+F die Menge der zu akzeptierenden Endzustände, wobei F eine Teilmenge von von Q ist.
+δ:Qx∑ ->Q ist die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen einen Nachfolgezustand zuordnet.
+Zudem gilt das Wort W zur Sprache L des Automaten gehört. wenn W ∈ ∑ ist und zu einem Endzustand F führt.
+=== Beispiel ===
+[[Datei:Nichtdeterministischer endlicher Automat NEA.jpg|mini]]
+Folgendes Diagramm stellt NEA und DEA gegenüber. Es wurde ein einfacher Spam-Filter als Automat entwickelt.
+== Potenzmengenkonstruktion ==
+Die Potenzmengenkonstruktion ist ein Verfahren, das einen nichtdeterministischen endlichen Automaten (NEA) in einen äquivalenten deterministischen endlichen Automaten (DEA) umwandelt.
+Die Zustände des aus dem NEA abzuleitenden DEA sind Mengen von Zuständen des NEA. Ein Zustand vom DEA kodiert dabei all diejenigen Zustände, in denen sich der äquivalente nichtdeterministische Automat NEA zu einem bestimmten Zeitpunkt befinden könnte. Ein Zustandsübergang im DEA ist deterministisch, da sein Folgezustand aus der Menge aller möglichen Folgezustände besteht, in die ein NEA unter einer bestimmten Eingabe gelangen kann. Das Verfahren heißt Potenzmengenkonstruktion, weil die Zustände des konstruierten Automaten Mengen von Zuständen des Ausgangsautomaten sind und daher die konstruierte Zustandsmenge Teil der Potenzmenge der Zustandsmenge des Ausgangsautomaten ist.
+Wir bertachten folgenden NEA als 5-Tupel (Quelle: https://de.wikipedia.org/wiki/Potenzmengenkonstruktion#Beispiele)
+Q: S0,S1,S2,S3
+S0∈Q
+∑:a,b
+F: S3
+δ:Qx∑ ->Q
+Die Übergangsfunktion des NEA lässt sich durch folgenden Graph beschreiben:
+[[Datei:NEA Beispiel.png|mini]]
 [[Kategorie:Automaten]]
 [[Kategorie:AHR_I_Informatik_LK]]