Diskussion:Potenzmengenkonstruktion

Ich wollte ja nicht nur nörgeln, deshalb habe ich den Artikel ergänzt und etwas korrigiert. Nun muss ich aber trotzdem noch rumnörgeln:

Da müssten wohl Verweise zu NEA/DEA hin, so dass man ein bisschen verstehen kann, worum es geht.

Ich kenne NEA-Definitionen, die gar keine $\epsilon$-Übergänge erlauben, sondern die nochmal anders bezeichnen: NEAS, ... mit spontanen Übergängen.

Diese Übergänge müßten auf jeden Fall in der Definition von ${\tilde {\delta }}$ berücksichtigt werden. Die jetzt gegebene Definition verstehe ich gar nicht, die sieht sehr falsch aus.

Und grundsätzlich finde ich den Begriff Potenzmengenkonstruktion nicht wichtig genug, um ihn aufzunehmen. Sicher, in einer TI-Prüfung muss man das schon kennen, aber man muss doch nicht jeden Beweis aufführen, der einen Namen hat. Nichts für ungut, aber ich denke, so richtig spannend findet man das nur, wenn man es gerade lernt und noch nicht ganz verstanden hat.

--Tian 22:28, 17. Mär 2004 (CET)

Zeichnungen der Automaten falsch?

Ich dachte, sobald ein Automat in seinem Endzustand angekommen ist, bleibt er dort und es finden keine Zustandsübergänge mehr statt. Wieso zeigen dann in den Zeichnungen dann noch Pfeile aus dem Endzustand wieder heraus? Irgendwas kann da nicht stimmen, oder? --RokerHRO 13:42, 5. Jul 2006 (CEST)

deine annahme ist falsch. es kann sehr wohl möglich sein, dass beim abarbeiten des eingabewortes der endzustand mehrfach durchlaufen wird. fürs akzeptieren ist lediglich wichtig, dass er am ende dort auch anhält. gruß --Murkel ^(anmurkeln) 15:02, 5. Jul 2006 (CEST)

Ich denke, dass die letzte Zeichnung (2. Beispiel, DEA) - wenn auch aus anderem Grund - dennoch falsch ist - ebenso wie die Tabelle direkt darüber ("neue" Abbildungsfunktion δ').

Die Zeichnung enthält mit dem Zustand 0 eine Sackgasse, die den Automaten nie terminieren läßt - was aber eigentlich schon pasieren sollte. Da die Abbildungsfunktion δ eines DEA keine totale Funktion sein muss, ist hier einfach der Übergang $(S'_{0},b)$ zusammen mit dem Zustand 0 und den Übergängen $(0,*)$ zu entfernen. In anderen Worten: der Zustand 0 ist midestens überflüssig.

Aus dem selben Grund muss bei der Tabelle der im Zustand $S'_{0}$ ermittelte Folgezustand 0 eigentlich auch eher $\emptyset$ sein - also kein Folgezustand. Die letzte Zeile der Tabelle wird damit natürlich obsolet und kann vollständig entfernt werden.

Sehe ich das richtig oder habe ich einen groben Denkfehler gemacht? Kann jemand meine Aussage bestätigen oder begründet widersprechen?

-- Aves83 10:07, 21. Okt. 2008 (CEST)

Okay, habe ich mich wohl getäuscht, δ muss wohl doch eine totale Funktion sein:

"A [...] DFA is a quintupel [...], where [...] δ [is] a total function from Q x Σ to Q known as the tranistion function." (Languages and Machines, Third Edition, Seite 147 (Definition 5.2.1) Thomas A. Sudkamp, ISBN 0321322215)

Damit ist das Beispiel natürlich doch korrekt und das hat sich erledigt - tut mir leid. --Aves83 03:42, 22. Okt. 2008 (CEST)

NEA mit mehreren Startzuständen

Hallo,

ich habe eine Bitte: Es wäre der Vollständigkeit halber sehr nett, wenn der Fall eines NEAs mit mehreren Startzuständen ebenfalls erklärt wird. Das ist im Artikel nirgendwo erwähnt, kann aber meines Wissens nach vorkommen. Bei dem Algorithmus zur Potenzmengenkonstruktion wird aber ausdrücklich von einem Startzustand (q0) ausgegangen.

Meines Wissen hat ein endlicher Automat immer genau einen Startzustand. Kannst du Literatur für endliche Automaten mit mehreren Startzuständen angeben? --Stefan Birkner 11:09, 23. Apr. 2007 (CEST)

Meines Wissens hat unser unbekannter Freund schon recht: wenn auch sehr unüblich, so kann ein NEA definitionsgemäß durchaus mehrere Startzustände haben. Siehe hierzu etwa auch den Artikel NEA. Eine Suche mit Google nach "mehrere Startzustände" NEA führt ebenfalls zu diversen ernstzunehmenden Quellen (u.a. Universitäten) die dies bestätigen.

Da der Artikel Endlicher Automat, der die NEAs ja mit abdecken sollte, aber von nur einem einzelnen Startzustand spricht, bin ich etwas verwirrt...ist das ein Fehler im Artikel? -- Aves83 10:28, 21. Okt. 2008 (CEST)

im fall des NEA ist die sache sehr einfach: mehrere startzustände sind natürlich möglich aber unnötiger aufwand, da alle diese zustände zu einem zusammengefasst werden können, von dem in er konsequenz mehrere zustandsübergänge möglich sind. gruß --Murkel ^(anmurkeln) 19:52, 21. Okt. 2008 (CEST)

Mit dem Zusammenfassen hast du natürlich recht, Murkel. Ein Beispiel ist damit wirklich überflüssig. Damit bleibt nur noch die Ungenauigigkeit im Artikel Endliche Automaten (zu denen NEAs ja auch gehören) im Abschnitt 'Das mathematische Modell'. Siehe auch auf der dortigen Diskussionseite. (Für diesen Artikel ist die Diskussion wohl beendet. ;-)) -- Aves83 20:53, 21. Okt. 2008 (CEST)

DEA => DFA und NEA => NFA

Hallo, also ich würde wie in der Überschrift die Abkürzungen entsprechend ändern. Dies ist zwar englisch (für deterministic finite automate), aber in der Fachliteratur (bei uns hier in der Vorlesung sowie diversen Büchern (bspw. Schöning)) gibt es keine DEA's, sondern nur DFA's. Das Gleiche beim NEA. Grüße --k00ni 18:13, 2. Aug. 2008 (CEST)

Bin ich auch dafür. --Unterstrichmoepunterstrich 09:16, 11. Feb. 2010 (CET)

Ich finde, hier sollte man konform mit den anderen Wikipedia-Seiten zum Thema bleiben (Bsp.: Deterministischer_endlicher_Automat). -- C.boelitz 16:47, 21. Feb. 2010 (CET)

Bildbeschreibung fehlt bei [[Bild:Nea03.png]] und [[Bild:Dea03.png]]

Der Artikel enthält ein Bild, dem eine Bildbeschreibung fehlt, überprüfe bitte, ob es sinnvoll ist, diese zu ergänzen. Gerade für blinde Benutzer ist diese Information sehr wichtig. Wenn du dich auskennst, dann statte bitte das Bild mit einer aussagekräftigen Bildbeschreibung aus. Suche dazu nach der Textstelle [[Bild:Nea03.png]] und [[Bild:Dea03.png]] und ergänze sie.

Wenn du eine fehlende Bildbeschreibung ergänzen willst, kannst du im Zuge der Bearbeitung folgende Punkte prüfen:

• Namensraum Datei: Bilder sollte im Namensraum Datei liegen. Bitte ändere die alten Bezeichnungen Bild: und Image: in Datei:.
• Skalierung: Außerhalb von Infoboxen sollten keine festen Bildbreiten (zum Beispiel 100px) verwendet werden. Für den Fließtext im Artikelnamensraum gibt es Thumbnails in Verbindung mit der automatischen Skalierung. Um ein Bild/eine Grafik in besonderen Fällen dennoch größer oder kleiner darzustellen, kann der „upright“-Parameter verwendet werden. Damit erfolgt eine prozentuale Skalierung, die sich an den Benutzereinstellungen orientiert. --SpBot 00:28, 2. Mär. 2009 (CET)

Nachvollziehbares, ausführlich erklärtes Beispiel fehlt

Die entsprechende Seite der englischen Wikipedia hat ein sehr ausführliches und nachvollziehbares Beispiel. Ich bin der Meinung das fehlt hier und schlage deshalb vor, es einfach zu übersetzen und zu übernehmen, evtl. sogar die aktuellen (teilweise oder ganz) zu ersetzen.

-- C.boelitz 16:41, 21. Feb. 2010 (CET)

Dem schliesse ich mich an. Die Theorie wie hier beschrieben ist leider ziemlich unverständlich... -- Fish-guts • Disk 13:21, 6. Mär. 2011 (CET)

Die Theorie ist hier besser beschrieben als im englischen Artikel, denn es gibt hier noch eine algorithmische Erklärung. Das erste Beispiel im englischen Artikel ist fast wie ein HowTo geschrieben ("We begin with", "We must consider", "We do this by", "Suppose we saw"). Das ist nicht sehr enzyklopädisch und ich denke, das kann man auch anders machen. Mit "nachvollziehbar" ist hier wohl gemeint, dass der Weg zu den Ergebnissen erklärt werden soll? Dafür wäre ein knapperes Beispiel als Beispiel 5.1 leichter nachzuvollziehen. Beispiel 5.2 hat einen "Sackgassen-Zustand", der nur benötigt wird, wenn man eine von zwei Definitionen für DEA heranzieht, passt hier aber vor allem nicht zum Algorithmus oder zur formalen Definition und müsste daher auch überarbeitet werden.

Das Beispiel aus dem englischen Artikel hat ebenfalls einen Sackgassen-Zustand, sodass entweder Algorithmus+Definition geändert werden müssten, oder die Grafiken. Einfach nur zu übersetzen ist außerdem eigentlich auch nicht zulässig, da man sonst die Urheberrechte missachtet (wg. Autorennennung). Wegen dieses Aufwands wäre es ganz gut, wenn die Frage nach einem "ausführlichen Beispiel" etwas konkreter gestellt würde. --Zahnradzacken

Epsilon-Schritte

Die Möglichkeit von Epsilon-Schritten ist eigentlich immer unnötig. Sollte man die vielleicht weglassen? Dann würde sich der "Formal"-Abschnitt nochmal erheblich vereinfachen: E fiele weg. Die Epsilon-Schritte vereinfachen mEn sowieso nur viel unkompliziertere Dinge, wie z.B. die Erzeugung eines Automaten für (L(A))* aus dem Automaten A. --Daniel5Ko 23:58, 18. Nov. 2010 (CET)

Das würde sooo einfach werden, dass folgende, 27 Zeilen kurze, Implementation alles essentielle enthält und z.B. durch GHC ge-typcheck-t werden kann:

import qualified Data.Set as S

data DFA s a = DFA s (a -> s -> s) (s -> Bool)

data NFA s a = NFA s (a -> s -> S.Set s) (s -> Bool)

bind :: Ord b => (a -> S.Set b) -> S.Set a -> S.Set b
bind f = S.unions . map f . S.toList

ret :: a -> S.Set a
ret = S.singleton

-- conversion
nfa2dfa :: Ord s => NFA s a -> DFA (S.Set s) a
nfa2dfa (NFA nstart ntrans nfinal) = DFA start trans final where
	start = ret nstart
	trans = bind . ntrans
	final = any nfinal . S.toList

-- two versions of a simple accept: one for NFA, one for DFA.
naccept :: Ord s => NFA s a -> [a] -> Bool
naccept = accept . nfa2dfa

accept :: DFA s a -> [a] -> Bool
accept (DFA start trans final) = h start where
	h s [] = final s
	h s (a:as) = h (trans a s) as

--Daniel5Ko 00:45, 19. Nov. 2010 (CET)

NFAs müssen nicht unbedingt Epsilon-Schritte können, das sagt einerseits schon der Artikel NEA und vor allem auch Juraj Hromkovič in "Theoretische Informatik". Andererseits gibt es eben auch die Definition mit Epsilon-Schritten und an dem, was schon im Artikel steht, ändert sich nicht viel: Im Abschnitt "Formal" fiele die Zeile mit "E:" weg, die nächste änderte sich zu $s'=\{s\}$ und die dann nächste zu

$\delta ':{\mathcal {P}}(Q)\times \Sigma \to {\mathcal {P}}(Q)$, mit $\delta '(q',a):=\bigcup _{p\in q'}\delta (p,a)$

So viel besser finde ich das nicht und man zahlt den Preis, dass man für die Möglichkeit der Epsilon-Schritte noch irgendwo einen Extrawurst-Abschnitt bräuchte.

Dein Code ist nett, ich finde ihn als Ungeübter aber schwer nachvollziehbar. Welche Rolle spielt f bei bind und wo kommt es dann her? trans = bind ntrans fände ich logischer. Siehst du in dem Code einen Mehrwert für den Artikel? --Zahnradzacken 21:52, 6. Mär. 2011 (CET)

Nun, ich fänd's ungefähr so ganz gut, hab' mich aber nicht besonders darüber informiert, in wie weit das schon irgendwo steht: Epsilonschritte sind unnötig, erleichtern aber einige Betrachtungen. Eine Umwandlung von NFAs mit Epsilon-Schritten zu NFAs ohne solche ist mehr oder weniger "Routine", und im vorliegenden Artikel ignorieren wir daher Automaten mit Epsilon-Schritten.

Zum Code: trans = bind . ntrans ist korrekt. Man beachte, dass trans eine gecurryte Funktion mit 2 Parametern ist: Eingabesymbol und Zustand. Äquivalent zu trans = bind . ntrans im Code für nfa2dfa ist trans a = bind (ntrans a). bind ist das normale monadische bind, hier instanziert für endliche Mengen. (Haskells >>= geht hier allerdings nicht direkt; zum einen, weil die Reihenfolge der Argumente andersherum ist, zum anderen, weil man aufgrund des Ord-Constraints nicht wirklich eine Monad-Instanz angeben kann.)

Ob der Code einen Mehrwert für den Artikel darstellt: Keine Ahnung, wahrscheinlich nicht. Er ist aber wenigstens typenmäßig automatisch checkbar. Und wenn man sich anschaut, wie falsch der "Formal"-Abschnitt schon auf Typebene vor meinen Änderungen war, könnte man zur Erkenntnis gelangen, dass vielleicht irgendwas nützliches dran ist. Mir hat er beim Korrigieren jedenfalls geholfen... --Daniel5Ko 22:49, 6. Mär. 2011 (CET)

Deine Korrekturen hatte ich nicht in Erinnerung. Jetzt sieht es ja sehr gut aus.

Zum Code: Achja, Currying. Danke für die Erklärung. Trotzdem ist der Code etwas unzugänglich und ich hätte es deshalb schwierig gefunden, ihn im Text unterzubringen.

Zur Sache: Verlangt man einen umfassenden Artikel, müsste man auch noch Algorithmus und Definition um den Fall ergänzen, dass man für DFAs eine totale Übergangsfunktion annimmt (und man dann manchmal noch den Sackgassen-Zustand braucht). So gesehen ist also ein Auslagern der Betrachtung von Epsilonschritten nur "gerecht". Wäre nur schön, wenn man die Betrachtung dann nicht völlig wegfallen ließe. --Zahnradzacken 19:56, 7. Mär. 2011 (CET)

Zur Totalität der Übergangsfunktion des DFAs: Die ist ohne Bedingung an den Eingabe-NFA immer realisierbar und steckt in der normalen Übersetzung schon drin. Die leere Menge ist ein Element der Potenzmenge der Zustandsmenge des Eingabe-NFAs, und somit ein gültiger Zustand des zu konstruierenden Automaten.

Dieser Zustand kann im Abschnitt "Konstruktion" in Schritt 3 entstehen. Aus ihm führt kein Weg heraus (bzw. alle Eingabezeichen führen wieder dort hin); und Endzustand ist er auch nicht. Im "Formal"-Abschnitt und in obigem Code ergibt sich $\delta '(\emptyset ,x)=\emptyset$ für alle $x\in \Sigma$ und $\emptyset \not \in F'$ ganz automatisch und auf natürliche Weise. Dieser Zustand ist der ggf. benötigte Sackgassenzustand.

Im ersten Beispiel entsteht so einer. Er ist lediglich in der Abbildung nicht eingezeichnet. Im dritten Beispiel entsteht auch einer, ist aber eingezeichnet, warum auch immer...

Damit kann man also nicht so recht argumentieren, dass das Ignorieren bzw. Auslagern der Betrachtung von Epsilon-Schritten nur gerecht wäre. :)

Nun ja, ich denke mal noch 'ne Weile drüber nach. Das Verfahren unter "Konstruktion" funktioniert 'zufälligerweise' auch mit Epsilon-Übergängen, wenn man Epsilon als normales Eingabezeichen ansieht; die Beispiele allerdings verwenden alle keinen Epsilon-Übergang.

Hmm... --Daniel5Ko 21:07, 7. Mär. 2011 (CET)

Ah, mich hat $Q'\subseteq {\mathcal {P}}(Q)$ etwas in die Irre geführt. Aufgrund der Totalität von $\delta '$ müsste automatisch $Q'={\mathcal {P}}(Q)$ gelten. Die Konstruktion weicht von der Definition dann aber tatsächlich zumindest insofern ab, als unerreichbare Zustände des NFA wegfallen und man dann keine totale Übergangsfunktion erhält (aber aus anderen Gründen als zunächst von mir vermutet).

Was meinst du mit "Epsilon als normales Eingabezeichen"? Vielleicht das, was ich einst unter Epsilon-Übergänge geschrieben habe? Das halte ich inzwischen für überarbeitungswürdig Behandelt man es im Algorithmus wie ein $s\in \Sigma$, dann versagt der Algorithmus, sobald mehrere Epsilonschritte hintereinander möglich wären. Trotzdem "kann" der Algorithmus auch Epsilonschritte, wenn man im Schritt 3 hinter dem Wort Erreichbarkeit auch die Epsilon-Hülle vermutet.

Da du ja sonst gerne mit dem Wiki-Prinzip argumentierst: Arbeite deinen Vorschlag in den Artikel ein und warte ab, ob es einen Edit-War gibt ;) --Zahnradzacken 22:38, 7. Mär. 2011 (CET)

(entrückt) Zur zweiten Hälfte: Ja, ich meinte das unter Epsilon-Übergänge. Der momentan unter "Konstruktion" angegebene Algorithmus funktioniert so, wie er ist, auch bei mehreren hintereinander möglichen Epsilon-Übergängen. (Jedenfalls fällt mir grad nix ein, wie man dem ein Bein stellen könnte. Selbst mit Zykeln aus Epsilon-Übergängen gibt's kein Problem. Oder sehe ich's bloß nicht? Gib mal ein konkretes Beispiel.)

Zur ersten Hälfte: Nein, der unter "Konstruktion" angegebene Algorithmus ermittelt nur die Teilmenge von ${\mathcal {P}}(Q)$ für $Q'$, die auch wirklich benötigt wird. Und über $Q'\times \Sigma$ mit dem minimal nötigen $Q'$ ist $\delta '$ total. Von welcher Definition weicht da was genau ab? Meinst du vielleicht, den Teil im "Formal"-Abschnitt:

$\delta ':{\mathcal {P}}(Q)\times \Sigma \to {\mathcal {P}}(Q)$, [...]

$Q'\subseteq {\mathcal {P}}(Q)$, sodass [irgendwas mit $\delta '$!]

? Falls dem so ist: Hmm, ja, da kann man vielleicht 'was machen, sodass $\delta '$ "wirklich" auch deklarationsmäßig total wird, ohne dass $Q'$ wegen Rekursion-ohne-Basisfall undefiniert bleibt. --Daniel5Ko 23:39, 7. Mär. 2011 (CET)

Zuerst zu deiner Änderung: Die Definition von $\delta '$ hängt nun von $Q'$ ab, dessen Definition aber wiederum von $\delta '$. Das halte ich für ungünstig :)

Dann zu deiner Frage, was wovon abweicht: Die Konstruktion wich von der Definition ab, weil die Konstruktion alle vom Startzustand $s_{0}$ aus erreichbaren Zustände betrachtet. Zustände, die schon in ${\mathcal {NA}}$ unerreichbar waren, sind dann in keinem $q'\in Q'$ enthalten, somit gilt dann $Q'\subsetneq {\mathcal {P}}(Q)$. Die Definition vor deiner Änderung sagte dagegen, dass $\delta '$ von ${\mathcal {P}}(Q)\times \Sigma$ abbildet, die Totalität der Funktion führte dazu, dass die von $\delta '$ abhängige Definition von $Q'$ auch vom Startzustand aus unerreichbare Zustände enthielt.

Zu Epsilon-Übergängen: Den Abschnitt muss ich dann wohl dringender überarbeiten, als ich dachte ;) Ich glaube, dass es richtiger ist, wenn man die Transitionsrelation von NEAs folgendermaßen erweitert: $\Delta \subseteq Q\times (\Sigma {\dot {\cup }}\{\varepsilon \})\times Q$. Das Epsilon hat eine Sonderrolle und sollte nicht als Symbol betrachtet werden, vor allem nicht bei Schritt 3 der Konstruktion, denn sonst hätte man die Epsilons auch noch beim DFA als Teil des Alphabets. Ich widerspreche meiner Aussage von früher am Abend, dass Schritt 3 bei $\varepsilon \in \Sigma$ versagt, wenn zwei Epsilon-Kanten aufeinander folgen. Das Problem ist eher Folgendes:

Wenn man beim NFA $(Q,\{a\},\Delta ,s_{1},\{s_{3}\})$ mit $Q=\{s_{1},s_{2},s_{3}\}$ und $\Delta (1,a)=\{2\}\;\;\Delta (2,\varepsilon )=\{3\}$ vom Startzustand $q'=\{s_{1}\}$ Schritt 3 anwendet, erhält man $q''=\bigcup \{\delta (r,a)|r\in q'\}=\{s_{2}\}$. Den Endzustand $s_{3}$ bekommt man nicht mehr in den DFA. Bei Einbeziehen der Epsilon-Hülle käme heraus: $q''=\{s_{2},s_{3}\}$.

Über all dem Argumentieren habe ich aber vergessen, was das alles dem Artikel nützt ;) Darüber mache ich mir morgen Gedanken. Grüße--Zahnradzacken 00:40, 8. Mär. 2011 (CET)

Vermutlich während du diesen Diskussionsbeitrag verfasst hast, habe ich weitere Änderungen vorgenommen. Ich hab' ein ${\tilde {\delta }}:{\mathcal {P}}(Q)\times \Sigma \to {\mathcal {P}}(Q)$ eingeführt, $Q'$ mittels ${\tilde {\delta }}$ definiert, und dann $\delta ':Q'\times \Sigma \to Q',\delta '={\tilde {\delta }}\downarrow (Q'\times \Sigma )$ gesetzt. Das ist nun zweifelsfrei unzirkulär. :)

Zum Epsilon-Übergang: Jupp, eine disjunkte Vereinigung wäre richtiger. Nichts desto trotz funktioniert der Algorithmus ganz problemlos, wenn man temporär, also nur während der Erzeugung des DFA, so tut, als sei $\varepsilon \in \Sigma$. Es gibt dann eben auch einen Schleifendurchlauf, der ein $q''=\bigcup \{\delta (r,\varepsilon )|r\in \{s_{2}\}\}=\{s_{3}\}$ erzeugt. --Daniel5Ko 12:38, 8. Mär. 2011 (CET)

Ach, ich bemerke gerade, dass das ja Quatsch ist. Würde man das wirklich tun, erhielte man im erzeugten DFA Epsilon-Schritte, was natürlich Quark wäre. Ich nehme alles zurück, und behaupte das Gegenteil. :) Algorithmus unter "Konstruktion" funktioniert nicht ohne weiteres bei Automaten mit Epsilon-Schritten. Somit ist der "Formal"-Abschnitt tatsächlich die einzige Stelle, im Artikel, die von ihnen Notiz nimmt. --Daniel5Ko 12:55, 8. Mär. 2011 (CET)