Informatiker Board | Theoretische Informatik | Automaten, kürzestes unterscheidendes Wort

Informatiker Board » Themengebiete » Theoretische Informatik » Automaten, kürzestes unterscheidendes Wort

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Automaten, kürzestes unterscheidendes Wort

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

C3P0
Grünschnabel

Dabei seit: 04.05.2011
Beiträge: 4

Automaten, kürzestes unterscheidendes Wort

Zitatantwort auf diesen Beitrag erstellen

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 [latex]z_1[/latex]

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 [latex]Z_f [/latex]

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 [latex]z_1[/latex]

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 [latex]z_2 [/latex]

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 [latex]|w| < |Z|^2 [/latex]

, 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

04.05.2011 14:05

Nehmen Sie C3P0 in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Automaten, kürzestes unterscheidendes Wort