Myhill Nerode Äquivalenzklassen bestimmen

26.11.2016, 13:37	felix_macht_info	Auf diesen Beitrag antworten »
Myhill Nerode Äquivalenzklassen bestimmen Meine Frage: Hey Forum, ich stehe momentan vor der Übungsaufgabe, die Äquivalenzklassen nach Myhill-Nerode Relation von L = {0,1}^* anzugeben. Wir haben grade erst mit dem Thema angefangen und ich bin mir noch sehr unsicher bzgl. der Äquivalenzklassen-Bestimmung. Könnt ihr mir vielleicht weiterhelfen? Meine Ideen: Meiner Meinung nach gibt es drei Äquivalenzklassen, einmal $\begin{eqnarray} [ \epsilon ] \end{eqnarray}$ = {0,1}^* = L, einmal $\begin{eqnarray} [ 0 ] \end{eqnarray}$ = 0(0\|1)^* und $\begin{eqnarray} [ 1 ] \end{eqnarray}$ = 1(0\|1)^* ist das soweit richtig? So wie ich das sehe, gibt es nur die Fälle $\begin{eqnarray} \epsilon \end{eqnarray}$ , oder dass das Wort mit 0 o. 1 anfängt. Danke für eure Hilfe!
06.07.2022, 16:34	Sry keine Ahnung	Auf diesen Beitrag antworten »
Ich weiß es auch nicht Mich würde eine Lösung des Problems auch freuen.
07.07.2022, 17:29	URL	Auf diesen Beitrag antworten »
RE: Ich weiß es auch nicht Ich hatte bis dato noch nie von dieser Relation und dem zugehörigen Kontext gehört. Also möge man meine Antwort mit Vorsicht genießen. Wenn ich den Wikiartikel zur Nerode-Relation richtig verstehe, dann gibt es auf $\begin{eqnarray} L=\{0,1\}^ \end{eqnarray}$ nur die Klasse L: Man kann zwei beliebige Wörter nehmen und mit einem beliebigen Suffix ergänzen und bleibt immer in L. Das Beispiel im Wikiartikel behandelt eine andere Grundmenge $\begin{eqnarray} L=0^1^ \end{eqnarray*}$ . Grob gesagt: Nach der ersten 1 kommen nur noch 1en

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »