 Automat zur Sprache |
grille1
unregistriert
 |
|
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
|
|
04.12.2015 20:53 |
|
|
grille1
unregistriert
|
|
Ich meinte natürlich L = {xz | x,z in {a,b}*, x ungleich z}
|
|
|
04.12.2015 20:55 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
05.12.2015 09:53 |
|
|
grille1
unregistriert
|
|
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.
|
|
|
05.12.2015 14:03 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Dann muss in meiner Argumentation irgendwo ein Fehler sein. Keine Ahnung wo 
Ich denke mal drauf rum.
Gruß,
Karlito
|
|
|
05.12.2015 15:09 |
|
|
grille1
unregistriert
|
|
Meinst du nicht, dass (ab)+ funktioniert? Hätte dann doch zwei Äquivalenzklassen, einmal epsilon und einmal alle anderen Wörter..
|
|
|
05.12.2015 15:23 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Nein, (ab)+ funktioniert nicht, da auch aab in der Sprache enthalten ist.
Gruß,
Karlito
|
|
|
05.12.2015 17:09 |
|
|
grille1
unregistriert
|
|
Und wenn man Epsilon mit reinnimmt, also (eab)+ und man für x einfach epsilon nimmt?
|
|
|
05.12.2015 17:44 |
|
|
grille1
unregistriert
|
|
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
|
|
|
05.12.2015 17:51 |
|
|
grille1
unregistriert
|
|
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
|
|
|
05.12.2015 23:50 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
| 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
|
|
|
06.12.2015 11:38 |
|
|
|
