Wie wurde die Äquivalenzklasse bzgl der Sprache A gebildet?

Question

Gegeben sei die Sprache:
$$A \triangleq\left\{1^{n} 0^{n} | n \in \mathbb{N}\right\} \quad \text { für } \Sigma_{A} \triangleq\{1,0\}$$

Und die Musterlösung:
$$ \begin{array}{l}{\left[1^{\mathrm{k}}\right]_{\equiv \mathrm{A}}=\left\{1^{\mathrm{k}}\right\} \quad \text { with } \mathrm{k} \in \mathbb{N}} \\ {[1^l0]_{\equiv \mathrm{A}}=\left\{1^{l+i-1} 0^{i} | i \geq 1\right\} \text { with } l \in \mathbb{N}^{+}} \\ {[0]_{=_{A}}=\left\{0 x, 1^{n} 0^{m}, x 01 y | x, y \in \Sigma_{A}^{*} \wedge n, m \in \mathbb{N}^{+} \wedge m>n\right\}}\end{array} $$

Meine Frage wäre, wie kommt man auf die zweite und dritte Zeile? Ich finde in der zweiten Zeile den Exponent undurchsichtig.
Ich glaube man versucht hier etwas zu zerlegen. Aber was genau ist der Sinn und warum ist i nicht definiert, also woher kommt das i eigentlich (R, N)?

Comments

Hat keiner eine Idee? Ich weiß, dass man es irgendwie in Suffixe zerlegen muss

---

Äquivalenzklassen gibt es bei einer Äquivalenzrelation. Um welche Äquivalenzrelation handelt  es sich in der Aufgabenstellung?

---

Hallo oswald,
ich hätte schwören können, Myhill nerode dazu geschrieben zu haben.

Also es geht um die Myhill nerode Klassen. Nur weiß ich ehrlich nicht wie man diese Bestimmt, ich kenne zwar die Formel, aber diese bringt mir in der Anwendung, wie oft nichts

Answer 1

Das Wort 1^l0 kann nur durch 0^l-1 zu einem Wort aus A ergänzt werden.

Die Frage ist, welche anderen Wörter nur durch 0^l-1 zu einem Wort aus A ergänzt werden können.

Beispiel. l = 3.

Das Wort 1³0 kann nur durch 0² = 0^3-1 zu einem Wort aus A ergänzt werden. Das ist wenig überaschend, schließlich ist das ja genau der Repräsentant, deren Äquivalenzklasse bestimmt werden soll

Aber auch Das Wort 1⁷·1³0·0⁷ = 1¹⁰0⁸ kann nur durch 0² = 0^3-1 zu einem Wort aus A ergänzt werden.

Werden also am Anfang mehrere Einsen und am Ende gleich viele Nullen angefügt, dann wird die Äquivalenzklasse nicht verlassen.

Allgemein.

Bezeichnet das i die Anzahl der Nullen in dem Präfix 1^m0ⁱ, dann wurde gegenüber dem Repräsentanten 1^l0 genau i-1 Nullen angefügt. Deshalb müssen auch i-1 Einsen vorangestellt werden, was dann zu m = l+i-1 Einsen führt.

Das Wort 0 kann nicht zu einem Wort aus A ergänzt werden. Äquivalenzklasse dieses Wortes ist also die Menge aller Wörter, die nicht zu einem Wort aus A ergänzt werden können. Diese Unterteilen sich in

• Wörter die mit 0 beginnen,
• Wörter der Form 1ⁿ0^m in denen mehr Nullen als Einsen vorkommen,
  
• Wörter in denen das Teilwort 01 vorkommt.

Comments

Hallo, danke für die Antwort.
Gibt es da irgendwelche Tricks? Ich finde es so schwierig die Klassen zu bilden, ehrlich gesagt habe ich es auch nicht ganz verstanden wie man die ganzen Klassen bildet, bzw worauf man achten muss.