Wie wurde die Äquivalenzklasse bzgl der Sprache gebildet?

 - (Schule, Mathematik, Informatik)

2 Antworten

Vom Fragesteller als hilfreich ausgezeichnet

Hilft dieser Wikipedia-Artikel weiter? https://de.m.wikipedia.org/wiki/Nerode-Relation

i ist offensichtlich ebenfalls eine natürliche Zahl.

Woher ich das weiß:Hobby – Hobby, Studium, gebe Nachhilfe

Hallo, danke für die Antwort und es tut mir leid für die Späte Antwort meinerseits.

Ich habe diesen und auch den englischen Artikel schon gelesen, mein Problem liegt darin, dass ich nicht weiß wie man diese Klasse bildet. Es liegt anscheinend am Suffix, der den Präfix (also eins der Elemente der einzelnen Klassen) zu der Sprache vervollständigt.Nur finde ich es sehr schwer eine Lösung zu finden und weiß auch nicht ob mein Gedankengang der Richtige ist.

0
@LunaMue

Kein Problem - ich hab ja auch erst am nächsten Tag geantwortet.

Zunächst: die 3. Äquivalenzklasse enthält genau diejenigen Elemente, die sich auf keine Weise nach rechts / durch ein Suffix zu einem Element von A ergänzen lassen. Nicht alle Elemente des Komplements von A gehören dazu, z. B. lässt sich 1^k durch 0^k zu einem Element von A ergänzen.

Die zweite Zeile enthält für jedes l diejenigen Elemente die sich durch (l-1) Nullen zu einem Element von A ergänzen lassen.

Die Klassen der 2. Zeile stimmen nicht mit denen der 1. Klasse überein, weil sich z. B. zwar sowohl 110 (2. Zeile) als auch 1 (1. Zeile) durch 0 zu einem Element von A ergänzen lassen, aber nur 1 auch durch 100, 110100 ist dagegen kein Element von A.

1
@PWolff

Der Exponent l+i-1 lässt sich an Beispielen erklären:

Nehmen wir diejenige Klasse, deren Elemente genau durch 000 zu einem Element von A ergänzt werden können. ("genau" heißt u. a., auf keine andere Weise, also 111 gehört nicht dazu - es lässt sich auch durch 10000 ergänzen.)

Das sind 11110, 1111100, 111111000, ...

Hier ist l=4, weil das kürzeste Element der Klasse 4 Einsen enthält.

i beginnt bei 1, wir haben für i=1 (4+1-1) Einsen und 1 Null, das ist das erste genannte Element 11110.

i=2 bedeutet (4+2-1) Einsen und 2 Nullen, 1111100, das 2. genannte Beispielelement.

Usw.

2
@PWolff

Ich denke morgen einmal darüber nach

0

Kannst du mal die gesamte Aufgabe posten, damit man überhaupt weiß, was eigentlich verlangt ist. Denn so ergibt das wenig Sinn.

Ups das wurde vergessen, sry.
Aufgabe: Gib alle Äquivalenzklassen der Myhill-Nerode-Relation bzgl. A an.

0
@jeanyfan

Schade, aber dennoch danke, vielleicht meldet sich morgen noch Jemand

0
@LunaMue

Mit solchen Fragen bist du als in irgendwelchen Fachforen besser aufgehoben.

0
@jeanyfan

Nun gibt es kaum gute Foren, wo man auh Antworten bekommt

0

Was möchtest Du wissen?