0 Daumen
615 Aufrufe
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.
von
σ(λ) = λ 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

1 Antwort

+2 Daumen
 
Beste Antwort

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.

von
Danke Dir :) Jetzt habe ich es auch kapiert!

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community