+2 Daumen
645 Aufrufe

bei dieser Aufgabe blicke ich gar nicht durch :(.

Bild Mathematik


Wie kann ich mir z:B. L5 überhaupt vorstellen?

Ich habe einige Male L5 rekursiv eingesetzt, sodass ich auf dieses MOnster komme:

Bild Mathematik

Beim besten Willen kann ich hier kein Muster erkennen.

Auf jeden Fall muss der 1.Buchstabe bei L5 und L6 ein a sein. Müsste der letzte Buchstabe bei L6 nicht auch ein a sein?

Wie geht man am besten an solche Aufgaben ran?


Über Hilfe wäre ich super dankbar ;)

mfg

haveagooday

Avatar von

mein * soll das Zeichen für die Konkatenation sein :)

1 Antwort

+2 Daumen
 
Beste Antwort
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.
Avatar von

Boah, super detaillierte Antwort! Zu sagen, dass hätte mir  sehr geholfen wäre noch eine  Untertreibung ;)!!


Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community