Endlicher Automat: Unterschied zwischen den Versionen

← Zum vorherigen Versionsunterschied Zum nächsten Versionsunterschied →

VisuellWikitext

@@ Zeile 122: / Zeile 122: @@
 [[Datei:NEA Beispiel.png|mini]]
+Nach obiger Konstruktion ergeben sich die Zustandsmenge Q′={S0′,S1′,S2′,S3′}  und die Übertragungsfunktion δ′ des äquivalenten deterministischen Automaten wie folgt:
+[[Datei:DEA Beipsiel.png|mini]]
+Neue Finalzustände sind die Zustände, die den Finalzustand des ursprünglichen NEA enthalten. Hier also S3′, da S3′ s3 enthält. Möglich ist, dass der abgeleitete DEA mehr Finalzustände besitzt als der zugrundeliegende NEA, da alle neuen Zustandsmengen die einen alten Finalzustände enthalten nun Endzustände sind. Insgesamt ergibt sich der deterministische Automat , der folgende graphische Darstellung besitzt:
+[[Datei:DEA Graph.png|mini]]
+== ε-NEA ==
+ε-NEAs sind ein nützliches Werkzeug in der Theorie formaler Sprachen und Automatentheorie. Sie bieten Flexibilität und können in vielen Fällen den Design- und Analyseprozess vereinfachen, da Sie es ermöglichen, Zustände ohne das Verarbeiten eines Symbols zu wechseln. Das kann in manchen Situationen die Konstruktion eines Automaten erleichtern. In manchen Fällen kann ein ε-NEA eine kompaktere und klarere Darstellung eines Problems oder einer Sprache bieten als ein NEA oder DEA.
+Um die Darstellung von endlichen Automaten zu vereinfachen, können  Zustandsübergänge  ohne Einlesen eines Zeichens ausgelöst werden. Diese Zustandsübergänge bezeichnet man als Epsilon-Übergänge. Für jeden nichtdeterministischen endlichen Automaten mit Epsilon-Übergängen gibt es einen nichtdeterministischen endlichen Automaten ohne Epsilon-Übergänge, der dieselbe Sprache erkennt, und umgekehrt. Die beiden Maschinenmodelle sind also äquivalent. Genau wie der normale nichtdeterministische endliche Automat erkennt ein nichtdeterministischer endlicher Automat mit Epsilon-Übergängen ein Wort w, wenn es in seinem Zustandsgraphen einen Pfad vom Startzustand zu einem Endzustand gibt.
+=== Umwandlung ε-NEA zu NEA ===
+Jeder ε-NEA lässt sich in einen NEA ohne ε-Übergänge umwandeln. Hierfür entfernt man die  ε-Übergänge und betrachtet die Zustandsmengen, die von den Zuständen Q inklusive ε-Übergänge erreicht werden können. Für diese resultierenden Zustandsmengen wird analog zum Verfahren der Potenzmengenkonstruktion ein NEA ohne ε-Übergänge abgeleitet.
+=== Beispiel ===
+Das folgende Diagramm beschreibt einen NEA mit ε-Übergängen. Dieser Automat lässt sich als 5-Tupel beschreiben:
+Q: 0-7
+S∈2
+∑:a,b,ε
+F: 3
+δ:Qx∑ ->Q
+Er wird in der Folge in einen NEA ohne ε-Übergänge umgewandelt.
 [[Kategorie:Automaten]]
 [[Kategorie:AHR_I_Informatik_LK]]