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