Als erstes solltest du dir klar machen dass die Mengenvereinigung U bedeutet, dass deine Ableitung entweder den linken Teil von U nimmt, oder den rechten. Man kann also nur eines der beiden involvierten Elemente ableiten. Dies ist ganz hilfreich, da man so riesige Verkettungen einfach auf kleinere herunter brechen kann. Das Monster wie du es nennst, solltest du schnell wieder verbannen ;-)
Nehmen wir L6:
Bedeutung der Mengennotation:
L6 = (€) oder (a * L6 * b) oder (b * L6 * a)
Du kannst also immer wenn du L6 ableitest, ein beliebiges dieser Elemente benutzen und damit L6 ersetzen. Hierzu sei zu sagen, dass es sogesehen unendlich viele unterschiedliche Ableitungen geben kann.
Mögliche Ableitungen (ein paar...):
- Das leere Wort
L6 --> €, der direkte Weg die Ableitung zu beenden, ohne überhaupt etwas zu sagen
- ab
L6 --> a * L6 * b --> a * € * b = ab
- ba
L6 --> b * L6 * a --> b * € * a = ba
- aabb
L6 --> a * L6 * b --> a * (a * L6 * b) * b --> aa * € * bb = aabb
- bababa
L6 --> b * L6 * a --> b * (a * L6 * b) * a --> ba * (b * L6 * ab) * a --> bab * € * aba --> bababa
Leicht zu erkennen ist, dass man das leere Wort benutzt um die Rekursion zum Abbruch zu führen.
Im Bezug auf Mustererkennung kann man für den Anfang (dank der 5 Ableitungen) sagen, dass L6 leer sein kann (€). Sowohl mit a als auch b anfangen und mit a und b enden darf. Gleichzeitig müssen immer genau so viele a wie b insgesamt im Wort vorkommen. Dadurch bedingt dass wir am "Rand" jeder Ableitung immer a und b, oder b und a zusammen haben, nie aber werden a oder b in L6 alleine abgeleitet.
Guck doch einfach mal ob es möglich ist Wörter in der Form abbaaa oder bbbbaabaaa zu erzeugen. Und wenn nicht, warum nicht. Da wir wie gesagt, von nahezu unendlich vielen potenziellen Ableitungen und Wörtern sprechen, ist es einfacher "Verbotenes" auszuschließen, als alle Wortkonstellationen durch zu probieren. Zusammen mit dem was dir bereits aus der Voraufklärung bekannt ist, wird es auf einmal ziemlich einfach die Wortmenge zu beschreiben.
a)
u = aabab, Anzahl a = 3, b = 2. Das Wort kann bereits nicht in L6 liegen wegen |a| != |b|
Zeigen kann man es auch, indem man die Ableitung zum scheitern bringt:
L6 --> a * L6 * b --> Widerspruch, da es eine Ableitung mit L6 --> a * L6 * a geben müsste.
Die einzigen 3 falschen Ableitungsmöglichkeiten sind ja eben:
L6 --> a * L6 * b --> a * € * b = ab != aabab
L6 --> a * L6 * b --> a * (a * L6 * b) * b = aa * L6 * bb --> aabb != aabab
L6 --> a * L6 * b --> a * (b * L6 * a) * b = ab * L6 * ab --> abab != aabab
Womit wir uns aber die Struktur zerschossen hätten. Aus z.B. aa*L6*bb kann eben niemals mehr aa*L6*ab werden. Die einzige Veränderung können wir in der Mitte mit L6 bewirken. Wir haben also keine Möglichkeit a gleichmäßig zu verteilen. Unterschiede bemerkt man, wenn man nach jedem Schritt an beiden Rändern von aussen nach innen gehend, die Korrektheit prüft.
Darüber hinaus kann man in L6 kein Wort mit ungerader Länge erzeugen. Entweder haben wir näherungsweise 4 oder 6 Buchstaben, aber keine 5. Es gibt also offensichtlich mehrere Kriterien. Festgelegt durch die Eigenschaft der Sprache (gezeigt habe ich 3), die man anwenden kann, um Wörter erbarmungslos zu diskriminieren.
Sowohl v als auch w können in L6 über Ableitungen erzeugt werden, und liegen deswegen auch in dieser Sprache. Die Ableitungen erfolgen analog zu meinem Beispiel oben, von bababa.
Wenn du weitere Fragen hast, kannst du gerne noch mal schreiben.
