Automaten, kürzestes unterscheidendes Wort

04.05.2011, 14:05	Auf diesen Beitrag antworten »
C3P0	Automaten, kürzestes unterscheidendes Wort Meine Frage: Hallo zusammen, ich bin bei der Vorbereitung auf meine Prüfung zur theoretischen Informatik auf folgende Frage gestoßen: Für einen bliebigen deterministischen endlichen Automaten ist die Länge des kürzesten, zwei Zustände und unterscheidenden Wortes stets kleiner gleich \|Z\|-1, wobei Z die Menge der Zustände ist. Es soll also für inäquivalente Zustände stets ein Wort w mit $[latex] \|w\| \leq \|Z\|-1[/latex]$ geben, für das o.B.d.A. $[latex]f(z_1,w) \in Z_f [/latex]$ und $[latex]f(z_2,w) \notin Z_f [/latex]$ , wobei die Menge der Finalzustände ist. Meine Ideen: Ich habe schon mehrere Ansätze ausprobiert, komme aber irgendwie nicht zum Ziel. Als erstes habe ich natürlich bemerkt, dass man mit einem Wort w mit $[latex]\|w\| \geq \|Z\|[/latex]$ immer irgendwo einen Kreis im Automaten läuft. Das Problem ist nur, dass ich diese Schlaufe hier nicht so ohne Weiteres "rausschneiden" kann. Wenn ich von aus mit w in einen Finalzustand laufe, kann ich das dann zwar auch mit einem kürzeren Wort, dieses könnte mich dann aber dummerweise von aus auch in einen Finalzustand führen, was ich ja nicht möchte. Außerdem gibt es durchaus Beispiele, in denen man Schlaufen laufen muss, um zwei Zustände zu unterscheiden. Oder übershe ich hier irgendwas? Als nächstes habe ich per Kreuzproduktkonstruktion einen Automaten gebastelt, der genau die unterscheidenden Wörter akzeptiert. Damit erhalte ich aber im Wesentlichen nur , die Abschätzung kann man noch ein klein wenig verbessern, aber an $[latex] \|w\| \leq \|Z\|-1[/latex]$ komme ich so nicht heran. Alternativ kann man sich auch direkt den Minimierungsalgorithmus ansehen, dann erhält man dieselbe Abschätzung. Zuletzt habe ich mir mal den Minimalautomaten angeguckt, o.B.d.A. kann ich ja zu diesem übergehen. Das könnte auch so gedacht sein, da der erste Teil der Aufgabe lautete: Zeigen Sie, dass in einem Minimalautomaten je zwei verschiedene Zustände inäquivalent sind. Also müsste ich jetzt zeigen können, dass es zu je zwei Äquivalenzklassen der [u] und [v] der Nerode-Relation ein w gibt, sodass o.B.d.A. $[latex]uw \in L[/latex]$ und $[latex]vw \notin L [/latex]$ (L die vom Automaten akzeptierte Sprache), wobei w weniger Buchstaben hat, als die Nerode-Relation Äquivalenzklassen hat. Das ist aber eigentlich nur eine Umformulierung des eigentlichen Problems und hilft mir wenig weiter. Kann man einen dieser Ansätze retten, oder muss man ganz anders rangehen? Bin für jede Hilfe dankbar! LG

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »