Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Homomorphismus
Hi,
Hoffe das hier mir jemand weiterhelfen kann …
Ich soll zeigen das A→A(R),S→S(R),s→[ s ] ein Homomorphismus ist…leider weiß ich nicht mehr wie man das macht und im Netz habe ich auch nix wirklich brauchbares gefunden…vielleicht kann mir ja jemand anhand der Aufgabe erklären wie man dieses macht.
Ich kann leider so ziemlich gar nichts mit der Aufgabe anfangen, aber der Nachweis, das irgendetwas ein Homomorphismus ist, lief normalerweise so, dass man sich alle Bedingungen anschaut, die ein H. erfüllt (das steht irgendwo im Skript oder den Vorlesungsaufzeichnungen oder Lexikon/Wikipedia) und sie dann mit dem Monster aus der Aufgabenstellung Schritt für Schritt nachprüft. So. Hoffe das war halbwegs verständlich.
Für einen Homomorphismus langt normalerweise z.z. dass alle Verknüpfungen mit dem Homomorphismus verträglich sind.
Also wenn du eine Struktur (A, +, , $) und eine (B, ", §, %) hast (+,,$,",§,% sind halt irgendwelche zweistelligen Verknüpfer) , die homomorph bzgl. f:A->B sein sollen, dann musst du nachrechnen ob
für x,y∈A gilt:
f(x+y)=f(x)"f(y)
f(x*y)=f(x)§f(y)
f(x$y)=f(x)%f(y)
Das wars schon.
Wenn du akut ein Beispiel brauchst, kannst du ja mal die komplette Aufgabe posten.
LOL der war gut das ist die Aufgabe 
aber schön zu wissen das ihr genauso wenig damit anfangen könnt :*)
Wo ist denn die Aufgabe her? Und nein, das kann nicht die komplette Aufgabe sein. (gibt algebraisch einfach keinen Sinn)
ist ne Übungsaufgabe von der FH(bin ja im moment dort aber vielleicht ab April wieder an der Uni 
) naja auf jeden Fall ist das eine reguläre Übungsaufgabe aus der Vorlesung steht halt nur das oben geschriebene dort ich konnte damit auch nix anfangen…keine Ahnung was das soll
Hab mal ein bißchen nachgedacht. Hier mein Ergebnis:
s→[ s ]
sieht wie ein Übergang zu Restklassen aus.
A→A(R)
S→S(R)
könnten Übergänge via von R erzeugten Nebenklassen sein.
letzteres würde dann aber 2mal das selbe darstellen.
Habt ihr villeicht im Script die Operationen A und S, sowie eine Äquivalenzrelation definiert (im Paragraph vor dieser ÜAufgabe/ blöde Frage, ich weiß)?
ich hab sicherheitshalber vorhin nicht gepostet, um nicht gefahr zu laufen mich lächerlich zu machen. 
meiner meinung nach ist die angabe unvollständig.
Kannst du einen Scan der Aufgabe ins Forum stellen?
Nicht, dass ich deine Abschreibkünste in Frage stellen würde, aber die Aufgabe ist so schon etwas seltsam.
Meine Hoffnung ist, dass man evtl. auf dem Scan ein Diagramm ergänzen oder ähnliches erraten kann.
Habe keinen Scanner aber habs mal abgemalt sieht wie immer sehr schlecht aus aber ist schon besser geworden
Attachment:
Aufgabe.JPG: https://fsi.cs.fau.de/unb-attachments/post_25393/Aufgabe.JPG
Aha H. von AUTOMATEN. Das macht schon mehr Sinn.
Bei s->[ s] sind dann die Nerode Äquivalenzklassen gemeint.
A->AuntenR sagt, das der Ausgangsautomat A in seinen (R wie reduziert) Minimalautomaten übergeht. S->SuntenR sind die übergänge des Alphabets (S wie Σ sieht man manchmal in älterer Literatur).
z.z: Struktur bleibt unter φ erhalten.
Bew: klar.
Naja gut, SPOILER:
Was gibt es denn für Struktur: Startzustände, Endzustände, sonstigezustände und Übergänge.
zu zeigen:1) jedes w∈L(A) ist auch in L(AuntenR) (von A, bzw AuntenR, akzeptierte Sprache).
2)jeder Startzustand geht in einen Startzustand, jeder Endzustand in einen Endzustand. Sonstige Zustände können natürlich verloren gehen.
Also los: Errinerung an die Konstruktion des Minimalautomaten:
Alle Zustände, mit gleicher Äquivalenzklasse gehen in den selben Zustand über.
Alle Äquivalenzklassen von Startzuständen gehen in Startzustände über,
Alle Äquivalenzklassen von Endzuständen gehen in Endzustände über.
Damit haben wir schon mal 2)
ad 1)
Sei w∈L(A), mit w=w1…wN, wI∈Σ
Dann hat man für einen Startzustand s ∈A, zwischenzustände zI und einen Endzustand e∈A folgendes Diagramm:
(Lies: s geht über w1 nach z1 geht über w2 nach…)
(s) -w1-> (z1) -w2-> (z2) -…->(z[N-1]) -wN> (e)
| | | | | von oben nach unten:φ
[ s] -w1-> [z1] -w2-> [z2] -…->[z[N-1]] -wN> [e]
Also gilt nach w ein Endzustand aus AuntenR.
q.e.d.
Halbwegs verständlich?
Wäre nett, wenn du hier postest ob ich recht habe, falls du es dann (nach der nächsten Übung?) genau weißt.
jo sieht ganz gut aus danke 