0 Daumen
1,3k Aufrufe

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)?

Avatar von

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

1 Antwort

+1 Daumen

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

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

Beispiel. l = 3.

Das Wort 130 kann nur durch 02 = 03-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 17·130·07 = 11008 kann nur durch 02 = 03-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 1m0i, dann wurde gegenüber dem Repräsentanten 1l0 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 1n0m in denen mehr Nullen als Einsen vorkommen,
  • Wörter in denen das Teilwort 01 vorkommt.
Avatar von 5,7 k

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community