Homomorphismus und Spiegelbildoperationen auf Wörtern

Question

Sei Σ ein Alphabet und sei σ : Σ∗→ Σ∗eine Operation, die für a ∈ Σ und w ∈ Σ∗definiert ist durch σ(λ) = λ, σ(wa) = aσ(w).

(a) Ein Homomorphismus ist eine Abbildung h : Σ∗→ Σ∗mit h(xy) = h(x)h(y) und h(λ) = λ. Ist σ ein Homomorphismus?Beweisen Sie Ihre Aussage.

(b) Bestimmen Sie schrittweise σ(w) fürΣ = {0, 1} und w = 1011 ∈ Σ∗.

(c) Zeigen Sie induktiv, dass σ der Spiegelbildoperation entspricht, d.h., dass σ(w) = sp(w) = wn· · · w1 für jedes w = w1· · · wn ∈ Σ∗gilt.


Joar, wäre super,wenn man mir hier helfen könnte :)

Präzision  λ ist das leere Wort.

Comments

σ(λ) = λ und was ist bei dir λ ? Das leere Wort?

---

Jau, genau :)

---

Also wenn ich das richtig sehe musst du in a) einfach überlegen ob aus σ(wa) = aσ(w)

für ein Wort w und einen Buchstaben a schon Folgen kann, dass σ(w1 w2) = σ(w1) σ(w2).

vielleicht hilft es dir einfach mal ein kleines Alphabet zu wählen und zu schauen was das heißt, dass σ(wa) = aσ(w) also zum Beispiel w=b ∈ Σ dann ist σ(ba) = aσ(b)=aσ(bλ) = abσ(λ)=abλ

was passiert jetzt mir längeren Wörtern?

---

Die können, wenn ich das richtig versteh, nach dem selben Prinzip gebildet werden?

---

Konkret, was ist σ(abc) wenn a,b,c Buchstaben

---

Jau, das wäre dann σ(abc) = aσ(bc) = σab(c) = aσ(bc) = abσ(c) bspw. 

---

Nein, das ist falsch,

σ(abc) = cσ(ab) = cbσ(a) = cbaσ(λ) = cba

---

Ah, okay, das kann sein. Danke Dir :)

Könntest du mir eventuell auch bei b und c helfen?

---

was hast du denn jetzt bei a) raus?

Homomorphismus oder nicht?

Ich muss mir die anderen mal kurz anschauen, ich hab sowas auch noch nie gemacht.

---

Habe geschrieben, dass es ein Homomorphismus ist.

---

Hast du das auch bewiesen? Das ist nämlich falsch, glaube ich. Ich formulier das mal als richtige Antwort, moment

Answer 1

in a) einfach überlegen ob aus σ(wa) = aσ(w)

für ein Wort w und einen Buchstaben a schon folgen kann, dass σ(w1 w2) = σ(w1) σ(w2).

Nehmen wir uns also mal die Buchstaben a,b,c,d,e,f ∈∑ und bilden die Worte abc, def ∈∑*

dann ist

σ(abc * def)= σ(abcdef) =f σ(abcde) = f * e * σ(abcd)= ... = fedcba σ(λ) =fedcbaλ =fedcba

wäre jetzt σ ein Homomorphismus, dann wäre auch

σ(abc * def) = σ(abc) * σ(def) = cba * fed =cbafed

es ist aber abcdef ≠ cba * fed

Also ist σ kein Homomorphismus.

 

Die Teile b) und c) laufen meines erachtens nach genau wie die Umformung oben ab.

Comments

Danke Dir :) Jetzt habe ich es auch kapiert!