Joejoe
Grünschnabel
Dabei seit: 30.05.2014
Beiträge: 4
 |
|
| Myhill-Nerode-Äquivalenzklassen |
     |
Meine Frage:
Hallo Zusammen!
Ich stehe hier vor dem Problem Myhill-Nerode-Äquivalenzklassen zu finden. Es geht primär um den Nachweis, dass eine Sprache nicht regulär ist.
z.B. für:
L={a^i b^i | i=j=2k für k>=1}
Meine Ideen:
Folgendes ist mein Ansatz:
Laut Definition gehören zwei Wörter einer Äquivalenzklasse an, wenn diese mit dem gleichen Suffix erweitert ein Wort der Sprache bilden. Zur Bildung dieser Äquivalenzklassen verwende ich sigma*. Stelle ich fest, dass es unendlich viele Äquivalenzklassen gibt, so ist die Sprache nicht regulär. Ist die Menge der Äquivalenzklassen endlich, so ist die Sprache regulär.
Zu oben genannter Sprache erhalte ich dann folgende Äquivalenzklassen:
[lambda]
[aab]
[a]
Allerdings habe ich festgestellt, dass eine unterschiedliche Anzahl von a's auch einen Suffix mit einer unterschiedlichen Anzahl von b's benötigt. D.h. [a^2k] müsste eine Menge von Äquivalenzklassen sein, von denen es dann doch offensichtlich unendlich viele gibt. Damit wäre die Sprache nicht regulär.
Liege ich mit meinen Annahmen richtig? Habt Ihr vielleicht einen Tipp wie man diese Äquivalenzklassen findet? Ich gehe eigentlich immer so vor:
Welche Worte kann ich mit der Sprache generieren (dann schreibe ich ca 10 auf)
Dann fasse ich einige Worte jeweils zu Äquivalenzklassen zusammen falls möglich
Zum Schluss schaue ich ob es eine Möglichkeit gibt unendlich viele Äquivalenzklassen zu erzeugen.
Ich bin mir allerdings NIE sicher, ob ich die Worte tatsächlich richtig zusammengefasst habe...
und eine wichtige Frage noch: Gehören die Worte, die NICHT in der Sprache sind EINER Äquivalenzklasse an?
Vielen Dank!
Liebe Grüße
Joejoe
|
|
