Diskussion:Nerode-Relation

Die bisherige Definition des Indexes einer Nerode-Relation was meines Erachtens fehlerhaft.
So hätte die Sprache 0*1* nach der bisherigen Definition unendlich viele Äquivalenzklassen, da es beliebig viele Suffixe (1, 11, 111, 1111, ...) gibt. Somit hätte sie auch einen unendlich großen Index. Da der Ausdruck jedoch (offensichtlich) regulär ist hat er einen endlichen Index. Ich habe mal versucht eine alternative Definition abzugeben und würde mich freuen wenn sie Jemand mal "korrekturliest" ;)

Gruß, Horratio

Die bisherige Definition war ungewöhnlich, aber nicht falsch. In der Tat kann der Index auf beide Weisen definiert werden. Beachte, dass die vorherige Definition nicht die Suffixe selbst zählt, sondern die Menge der Suffixsprachen; und die ist auch bei deinem Beispiel endlich, da gilt:

• Suffix(0) = Suffix(00) = ... = Suffix(0*) = {0*1*} = L
• Suffix(01) = Suffix(001) = Suffix(011) = ... Suffix(0*1*) = {1*}

Beachte, dass die Sprache 0*1* nur zwei Äquivalenzklassen aufweist! Sie kann durch einen Automaten mit nur zwei Zuständen erkannt werden: Der akzeptierende Zustand A wird mit 0 in sich selbst überführt und mit 1 in den akzeptierenden Zustand B, der wiederum mit 1 in sich selbst überführt wird. --Θ~ 00:57, 30. Jan 2006 (CET)

Dieses Beispiel hatte ich so in einer Vorlesung. Die Argumentation war, daß auch alle nicht in der Sprache enthaltenen Worte eine eigene Klasse bilden. Über die Anzahl der Knoten argumentiert könnte man also sagen, daß stets ein totaler Automat benötigt wird welcher einen "Ablehnenden" Endzustand für alle nicht enthaltenen Worte enthält. Ich könnte mir jedoch durchaus vorstellen, daß es hierfür keine Präzise Definition gibt und beides korrekt ist ;)

Ja, du hast natürlich recht, ich habe nicht alles durchdacht. Es fehlt der dritte, nichtakzeptierende Zustand, in den man vom zweiten aus mittels der 0 gelangt. Es hat schon seinen Grund, warum ich nachts nichts an mathematischen Artikeln ändere ;-). Die fehlende Suffixsprachen-Klasse ist Suffix(10) = Suffix(110) = ... = Suffix(0*11*0) = {}, also die leere Menge. Die verquere Suffixsprachen-Definition stammt aus einer meiner Vorlesungen :-) --Θ~ 13:47, 30. Jan 2006 (CET)

"*Die Äquivalenzklasse [1] besteht aus Folgen von Einsen (also $1^{+}$)"

Ich befuerchte, das ist so nicht ganz korrekt. In dieser Aequivalenzklasse [1] liegt auch z.B. 01 oder 00011, also allgmein alle Woerter aus $\Sigma ^{*}$, die ein beliebig langes Praefix an Nullen, gefolgt von einem Suffix von Einsen besitzen. Also muesste es heissen $[1]=0^{*}1^{+}$

Das seh ich genauso, drum hab ich's geändert ;-)

Du solltest noch ind(L) definieren, da es im letzten Absatz genannt wird. Wenn du ein nichtreguläres Beispiel suchst, kannst du 0^k1^k verwenden. --134.155.8.81 13:15, 14. Jan. 2008 (CET)

Link

Hi, ich hab nur nen Link auf Regulärer Ausdruck gesetzt... -- 178.24.208.117 11:31, 28. Nov. 2010 (CET)

Reguläre Ausdrücke vs. Mengenoperationen

Die Version vor meiner ebigen Änderung hatte reguläre Ausdrücke (wie $0^{*}1^{+}$) mit Mengenoperationen (wie $\{0\}^{*}\{1\}^{+}$) gemischt; das war etwas unsauber. Ich habe mich für Mengenoperationen entschieden. -- UKoch 18:52, 9. Dez. 2011 (CET)

Unsauber war auch, dass mal $L^{*}$ und mal $L^{\star }$ geschrieben wurde. Ich habe $^{\star }$ für den regulären Ausdruck stehen gelassen, auch wenn das kleinlicher ist, als im Artikel zu regulären Ausdrücken. --Zahnradzacken 00:59, 10. Dez. 2011 (CET)