---

Geschrieben von grille1 am 04.12.2015 um 20:53:

  Automat zur Sprache

Hallo!

Wir haben die Aufgabe bekommen, einen Index von einer Äquivalenzrelation zu zeigen sowie Äquivalenzklassen anzugeben. Dazu haben wir eine formale Sprache vorliegen, mit der wir dies erledigen sollen, die wir jedoch nicht ganz verstehen bzw. wissen wollen, ob unsere Vermutung richtig ist. Sie lautet:

L = {xz | x,z in {a,b}*, x ungleich y}

Wenn man die Sprache nun umformt, kann man dann sagen, dass hier {a + b}+ vorliegt?

Oder bedeutet am Anfang das xz eine Konkatenation, wo man dann sagen kann, dass {ab}* gilt?

Wir sind dankbar für jede Hilfe.

Liebe Grüße

---

Geschrieben von grille1 am 04.12.2015 um 20:55:

  RE: Automat zur Sprache

Ich meinte natürlich L = {xz | x,z in {a,b}*, x ungleich z}

---

Geschrieben von Karlito am 05.12.2015 um 09:53:

 

Hallo grille1,

x und z sind jeweils Wörter aus {a,b}*. Wären x und z gleich, so wäre xz ein Palindrom. Die Sprache ist also die Menge aller Wörter ungerader Länge oder Nichtpalindrome gerader Länge.

Die Nerode-Relation ist nun so definiert, dass zwei Wörter x und y genau dann Äquivalent zueinander sind, wenn der gleiche Suffix z dazu führt, dass xz und yz beider auch wieder Element der Gegebenen Sprache sind.

Nehmen wir also zwei beliebige Wörter. Sei x aus {a,b}*, so ist ausschließlich xx nicht in der Sprache enthalten. Sei y aus {a,b}*, so ist ausschließlich yy nicht in der Sprache enthalten. Wenn x und y nicht gleich sind, so ist xy Beispielsweise in der Sprache und xx nicht und umgekehrt. Es lassen sich also keine zwei Wörter finden, welche lt. Nerode-Relation äquivalent sind. Folglich bildet jedes Wort x aus {a,b}* eine eigenen Äquivalenzklasse und da es unendlich viele Wörter über {a,b}* gibt, ist der Index unendlich.

Gruß,

Karlito

---

Geschrieben von grille1 am 05.12.2015 um 14:03:

 

Danke schon mal für die Antwort . Problem ist nur, wir müssen zeigen, dass der Index 2 ist und welche Äquivalenzklassen es gibt. Geht natürlich nur, wenn man die Sprache überhaupt versteht. Der Index kann nur dann nicht unendlich sein.

---

Geschrieben von Karlito am 05.12.2015 um 15:09:

 

Dann muss in meiner Argumentation irgendwo ein Fehler sein. Keine Ahnung wo

Ich denke mal drauf rum.

Gruß,

Karlito

---

Geschrieben von grille1 am 05.12.2015 um 15:23:

 

Meinst du nicht, dass (ab)+ funktioniert? Hätte dann doch zwei Äquivalenzklassen, einmal epsilon und einmal alle anderen Wörter..

---

Geschrieben von Karlito am 05.12.2015 um 17:09:

 

Nein, (ab)+ funktioniert nicht, da auch aab in der Sprache enthalten ist.

Gruß,

Karlito

---

Geschrieben von grille1 am 05.12.2015 um 17:44:

 

Und wenn man Epsilon mit reinnimmt, also (eab)+ und man für x einfach epsilon nimmt?

---

Geschrieben von grille1 am 05.12.2015 um 17:51:

 

Wenn man (a+b)+ sagt, dann wäre aab ja nicht mehr mit dabei, nur epsilon fehlt ja komplett und kann dann ja keine Äquivalenzklasse bilden, es muss aber 2 geben

---

Geschrieben von grille1 am 05.12.2015 um 23:50:

 

Bei der sprache L = {xhz | x,z in {a,b}*, x ungleich z} soll bspw. gezeigt werden, dass der Index unendlich ist. Würde die Beschreibung von dir darauf passen?
LG

---

Geschrieben von Karlito am 06.12.2015 um 11:38:

 

Zitat:

Original von grille1 Bei der sprache L = {xhz | x,z in {a,b}*, x ungleich z} soll bspw. gezeigt werden, dass der Index unendlich ist. Würde die Beschreibung von dir darauf passen? LG

Was soll denn h sein?

Ich bleibe auch bei der anderen Aufgabe bei meiner Argumentation. Jeder Präfix (hier gleichzeitig die Äquivalenzklasse) führt zu einer anderen Menge von Suffixen, die erlaubt sind. Diese Mengen sind disjunkt, so dass jeder Präfix seine eigenen Äquivalenzklassse bildet.

Gruß,

Karlito