Monoide und Konkatenation

Question

Hallo:)

über jegliche Hilfe, wäre ich wirklich dankbar:)

Sei Σ = {a,b} und bezeichne Σ* das Monoid der endlichen Wörter über Σ mit Konkatenation als Verknüpfung (genauer: Σ∗ ist das freie Monoid über Σ).  Für ein Wort w ∈ Σ∗ bezeichne |w|_a die Anzahl der Vorkommen von a in w und |w|_b die von b. Damit defnieren wir auf Σ^∗ die Relation ∼⊆ Σ^∗×Σ^∗ über u ∼ v ⇐⇒ |u|_a = |v|_a und |u|_b = |v|_b.

Die Menge der natürlichen Zahlen N = {0,1,...} bildet mit der Addition als Verknüpfung ebenfalls ein Monoid. Mit N² bezeichnen wir das direkte Produkt dieses Monoids mit sich selbst, d.h. das Monoid, dessen Element Paare natürlicher Zahlen sind, mit der Verknüpfung

(m,n)(m',n') = (m + m',n + n').

 Zeige: Σ^∗/∼ ist isomorph zu N²

Comments

Und was ist Σ^∗/∼?

---

Ich vermute, dass die Fragestellung inzwischen vollständig(er) ist. Formale Sprachen wurden relativ häufig in die Stacklounge verschoben. Daher diese Frage auch. Es gibt in beiden Lounges eine Rubrik "ähnliche Fragen". Kann sein, dass dies hundertantworten bereits genügt (?).

Das soll aber niemanden daran hindern, eine Antwort zu versuchen :)

---

Und was ist Σ∗/∼?

Zwei Wörter stehen zueinander in der Relation ∼ wenn sie aus gleich vielen a und gleich vielen b bestehen, d.h., wenn sie sich nur in der Reihenfolge der Buchstaben unterscheiden oder überhaupt gleich sind.

Answer 1

Sei f: Σ*/~ →ℕ², [x] ↦ (|x|_a, |x|_b).

Wegen |u|_a = |v|_a und |u|_b = |v|_b für jedes u,v ∈ [x], ist f wohldefiniert.

f ist injektiv, weil

    (|u|_a, |u|_b) = (|v|_a, |v|_b)

    ⇒ |u|_a = |v|_a ∧ |u|_b = |v|_b

    ⇒ u ~ v

    ⇒ [u] = [v]

f ist surjektiv weil f([aⁿb^m]) = (n,m) für jedes (n,m) ∈ ℕ² ist.

Also ist f bijektiv.

Du musst noch zeigen, dass f ein Homomorphismus ist, dass also

    f([u][v]) = f([u]) f([v])

ist.