| Die letzten 10 Beiträge |
| Karlito |
| 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 |
| 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 |
| grille1 |
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 |
| grille1 |
Und wenn man Epsilon mit reinnimmt, also (eab)+ und man für x einfach epsilon nimmt? |
| Karlito |
Nein, (ab)+ funktioniert nicht, da auch aab in der Sprache enthalten ist.
Gruß,
Karlito |
| grille1 |
Meinst du nicht, dass (ab)+ funktioniert? Hätte dann doch zwei Äquivalenzklassen, einmal epsilon und einmal alle anderen Wörter.. |
| Karlito |
Dann muss in meiner Argumentation irgendwo ein Fehler sein. Keine Ahnung wo 
Ich denke mal drauf rum.
Gruß,
Karlito |
| grille1 |
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. |
| Karlito |
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 |
| grille1 |
RE: Automat zur Sprache
Ich meinte natürlich L = {xz | x,z in {a,b}*, x ungleich z} |
| Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen. |
|
|
