Aufgabe 10.2

[Thomas]

L = {a^n b^m| (2n-m) mod 5 = 0} (n, m € N) was meint ihr könnte man das so schreiben?

[SLS]

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

1. Es gilt:
(Von jedem Zustand landet man nach Eingabe von 'a' genau dort, wo man nach Eingabe von 'bbb' landet)
2. Gegeben sei ein Eingabewort . Ersetze nun jedes 'a' in durch 'bbb' (Das kann man auch formal beschreiben, indem man eine Funktion rekursiv definiert, die dieses Ersetzen durchführt), und nenne das Ergebnis .
3. Nun besteht nur aus b's (genauer aus b's (*)), wobei die Eingabe von zu demselben Endzustand führt, wie die Eingabe vom ursprünglichen .
4. Von allen möglichen Wörtern , die keine a's enthalten (also das leere Wort , oder nur b's), werden offensichtlich genau diese akzeptiert, für die folgendes gilt:

5. Mit (*) muss dann gelten:
6. Antwort ist dann:
-----
0. Alternativ (wenn man jedes 'b' durch 'aa' ersetzt):
00. Noch alternativer (Es werden die Namen der Zustände verwendet). Es gilt:
und
Ich werde es euch hier nicht vorführen, aber daraus ergibt sich:

-----
Alle drei Antworten (man kann auch andere rausbekommen) sind äquivalent. Zum Beispiel:
Es gelte .
Dann: , wobei gerade ist ().
Folglich:
Es gilt:
Folglich:
Analog zeigt man, dass wenn eine der Bedingungen erfüllt ist, dann sind alle erfüllt (das habe ich ehrlich gesagt nicht überprüft, aber ich bin 99% sicher, dass es
stimmt). Somit sind die Antworten äquivalent.
-----
Kurz über die Schreibweise: Wir haben inzwischen diese Woche gelernt, dass es immer (insbesondere hier) möglich ist, die Sprache, die von einem endlichen Akzeptoren akzeptiert wird, als regular expression anzugeben (und somit auch durch ).
Also es gibt so eine Darstellung der Antwortssprache. Hiermit fordere ich aber jeden von euch auf, der so eine Antwort gibt, deren Richtigkeit zu beweisen.
Das wäre (für mich zumindest) eine schwierige Aufgabe - zwar kann man sehr leicht beweisen, dass alle Wörter in der gegeben Sprache akzeptiert werden, aber es ist viel komplizierter zu beweisen, dass die gegebene Sprache wirklich alle Wörter beinhaltet, die der Automat akzeptiert.

Ich hoffe, mein langer Post hilft vielen weiter und zwar nicht unbedingt nur mit der eigentlichen Aufgabe hier, sondern i. A. die Denkweise (die ich jedenfalls toll finde ) zu verstehen.

Bis die Tage.

P.S. ist toll! Ich konnte es bis vor einem Monat fast überhaupt nicht, aber nun kann ich solche komplizierte Formel wie oben sehr schnell schreiben