Wie sieht es eigentlich bei einen Homomorphismus aus mit der Eigenschaft (nicht) regulär zu sein . Überträgt sich die von der Ursprache auf die Bildsprache und umgekehrt?

(Ich nehme mal an, du meinst Homomorphismen zwischen Sprachen,
also der Form [img]http://mokrates.de/cgi-bin/texstring?h%3A%5CSigma%5E*%5Crightarrow%5CGamma%5E*[/img] mit Alphabeten [img]http://mokrates.de/cgi-bin/texstring?%5CSigma%2C%20~%5CGamma[/img]).

Ja. Denn einerseits ist die Bildmenge eines solchen Homomorphismus
ja dieselbe wie die der zugehörigen Substitution s mit [img]http://mokrates.de/cgi-bin/texstring?s(w)%3A%3D%5C%7Bh(w)%5C%7D[/img].
Damit überträgt sich die Regularität vom Urbild auf das Bild.
Und dass die Urbildmenge einer regulären Menge unter einem solchen
Homomorphismus auch regulär ist, steht als Theorem im Skript.

Daraus folgt dann auch, dass sich die Eigenschaft nicht regulär zu
sein, auf Bildmengen überträgt: Ist L nicht regulär, so kann auch
h(L) nicht regulär sein. Denn wäre die Menge h(L) regulär, so
müsste es auch ihr Urbild L sein, was ein Widerspruch ist. Analog
zeigt man, dass inverse Homomorphismen diese Eigenschaft erhalten.

Und dass die Urbildmenge einer regulären Menge unter einem solchen
Homomorphismus auch regulär ist, steht als Theorem im Skript.

Welches Theorem soll das denn sein? Der inverse Homomorphismus betrachtet ALLE möglichen Urbilder, nicht nur die, die bei [img]http://mokrates.de/cgi-bin/texstring?$M:=h(L)$[/img] für M verwendet wurden! Daher ist das Folgende:

Daraus folgt dann auch, dass sich die Eigenschaft nicht regulär zu
sein, auf Bildmengen überträgt: Ist L nicht regulär, so kann auch
h(L) nicht regulär sein. Denn wäre die Menge h(L) regulär, so
müsste es auch ihr Urbild L sein, was ein Widerspruch ist. Analog
zeigt man, dass inverse Homomorphismen diese Eigenschaft erhalten.

falsch:

Sei [img]http://mokrates.de/cgi-bin/texstring?$L%5Cin%20%5CSigma%5E*$[/img] eine nichtreguläre Menge und [img]http://mokrates.de/cgi-bin/texstring?$h:%5CSigma%5E*%5Cto%5CSigma%5E*$[/img] definiert durch [img]http://mokrates.de/cgi-bin/texstring?$h(x):=%5Clambda$[/img] für jedes [img]http://mokrates.de/cgi-bin/texstring?$x%5Cin%5CSigma$[/img],
dann ist [img]http://mokrates.de/cgi-bin/texstring?$h(L)=%5C%7B%5Clambda%5C%7D$[/img] selbstredend regulär, nur L deswegen noch lange nicht!


theorinix

Oh, das stimmt! Da habe ich mich vertan.
[img]http://mokrates.de/cgi-bin/texstring?h%5E%7B-1%7D(h(L))[/img] muss natürlich nicht gleich L sein.

Und wenn ich mich nicht schon wieder irre, gibt es sogar
zu jedem Homomorphismus, der nicht injektiv ist, eine nicht
reguläre Sprache, die auf eine reguläre Sprache abgebildet
wird.

Da stellt sich die Frage: wann ist ein Homomorphismus
injektiv? Gibt es da eine einfache Charakterisierung?
(EDIT: Abgesehen von der, dass sie nicht-reguläre
Sprachen auf nicht-reguläre Sprachen abbilden [img]http://www.fb18.de/gfx/28.gif[/img])

Ich habe mir mal Gedanken über Injektivität von
Homomorphismen gemacht:

Die Menge der Wörter in der Bildmenge, die mehr als
ein Urbild haben, ist immer regulär und wird von einem
effektiv konstruierbaren NFA akzeptiert, wenn
[img]http://mokrates.de/cgi-bin/texstring?h%3A%5CSigma%5E*%5Crightarrow%20%5CGamma%5E*[/img] etwa beschrieben ist durch
[img]http://mokrates.de/cgi-bin/texstring?h(x_1)%5C%23h(x_2)%5C%23...%5C%23h(x_n)[/img]
mit [img]http://mokrates.de/cgi-bin/texstring?%5CSigma%3D%5C%7Bx_1%2C%5Cldots%2Cx_n%5C%7D%2C%20%5C%23%5Cnotin%5CGamma[/img]. Insbesondere
ist die Injektivität entscheidbar (wegen der Ähnlichkeit
zum PCP könnte man ja das Gegenteil vermuten).

Das heißt also: Wenn du wissen willst, ob ein gegebener
Homomorphismus Nichtregularität erhält, musst du prüfen,
ob er injektiv ist und das lässt sich ausrechnen.

Falls sich jemand für die Beweise (für "injektiv" gdw.
"Nichtregularität erhaltend", Regularität der Menge der
Wörter mit mehr als einem Urbild) bzw. das
Konstruktionsverfahren für den NFA interessiert, würde
ich das auch posten.

Hey Georg, ich nehme an, Du weißt nicht wem Du da gerade widersprichst…[img]http://www.fb18.de/gfx/15.gif[/img]

Ich widerspreche niemandem, ich bekräftige seine Aussage ja nur [img]http://www.fb18.de/gfx/23.gif[/img]

Ich habe ursprünglich irrtümlich behauptet, alle Homomorphismen
erhielten Nichtregularität, worauf theorinix ein Gegenbeispiel
angab. Und dann habe ich beschrieben, welche Homomorphismen
Nichtregularität erhalten (wenn schon nicht alle). Und zwar
sind es genau die Injektiven. Und jetzt kam noch hinzu, dass
man sogar ausrechnen kann, ob ein gegebener Homomorphismus
injektiv ist und, dass die Menge der Wörter, die mehr als ein
Urbild haben, regulär ist.

Edit: Ups, der zitierte Beitrag wurde wohl gelöscht.

Entschuldige bitte, ich hatte die Postings von hinten nach vorn gelesen und die Dinge missverstanden…
Deswegen habe ich auch schnell mein Posting gelöscht. sorry