In der zweiten Aufgabe wird gefragt, ob die durch den homomorphismus erzeugte Menge regulär ist.
Würde es nicht reichen zu zeigen, dass die Menge {a,b}* regulär ist, indem man sonen billigautomaten mit einem Zustand angibt und danach argumentiert, dass ein Homomorphismus eine strukturerhaltende Abbildung ist?
Folglich auch die Menge, die der Homomorphismus erzeugt regulär sein muss?
Das klingt jetzt ziemlich billig, aber in der Aufgabenstellung wird ja extra darauf hingewiesen, dass es ein Homomorphismus ist und keine einfache Abbildung…

Halt, Halt, Halt [img]http://www.fb18.de/gfx/23.gif[/img] Das ist doch gar nicht das, was in der Aufgabe passiert! {a,b}^* ist natürlich regulär und wenn man dadrauf eine reguläre Substitution anwendet (die ein spezieller Homomorphismus ist - und hier kann man in der Tat g und h als solche ansehen (wobei man eigentlich auf Mengen abbilden müsste, aber die werden einelementig, also ist das fast das gleiche)), dann ist die "entstehende" Menge auch regulär (vgl. Theorem 3.63, S.85). Da g und h solche sind (s.o.) ist g({a,b}^*) und auch h({a,b}^*) regulär, aber diese haben nichts mit der Sprache in der Aufgabe zu tun!! Genau hingucken wie das dort definiert ist (h(w) = g(w)) !!

Ein Gegenbeispiel (zu deinem Beweisversuch):

L := { w \in {a}^* {b}^* | g(w) = h(w) }

wobei g,h: {a,b}^* —> {c}^* durch g(a) := c, g(b) := lamda und h(a) := lambda, h(b) := c definiert seien.

{a}^* {b}^* ist nun regulär, obiges L aber nicht! Warum? g bildet ein Wort w gerade auf ein Wort ab, dass nur aus c's besteht und zwar aus genau sovielen wie in w a's auftraten. h bildet ein Wort w auf ein Wort ab, dass auch nur aus c's besteht und zwar aus genau sovielen wie in w b's auftraten. Gilt g(w) = h(w) hat w also gleich viele a's wie b's. Da die a's vor den b's kommen (w \in {a}^* {b}^*) ist also L = DUP, die ja nicht regulär ist.
Bei diesem Beispiel führt deine Argumentation (die du ja genauso führen könntest) also nicht zum Erfolg.


Dann frage ich nochmal ganz direkt (eine höfflichere Formulierung ist mir gerade nicht eingefallen, bitte nicht übel nehmen [img]http://www.fb18.de/gfx/28.gif[/img]): Ist dir überhaupt klar, was es bedeutet, wenn man sagt ein Homomorphismus sei eine "strukturerhaltene" Abbildung?

Wenn ich nämlich bspw. die nicht reguläre Menge DUP nehme (a^n b^n) und darauf einen Homomorphismus anwende, der a und b beide auf a abbildet. Dann wird die Menge DUP abgebildet auf {aa}^* (was eine reguläre Menge ist). Wird hier die "Struktur" erhalten?

Hoff' es wird klarer [img]http://www.fb18.de/gfx/22.gif[/img]

Cheers,
Frank

jo danke
1. Aufgabenstellung nicht richtig gelesen
2. war davon ausgegangen, dass strukturerhaltend sich auch darauf bezieht, Gegenbeispiel hats ja easy widerlegt :)
thx