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 N2 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 N2
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 :)
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.
Sei f: Σ*/~ →ℕ2, [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([anbm]) = (n,m) für jedes (n,m) ∈ ℕ2 ist.
Also ist f bijektiv.
Du musst noch zeigen, dass f ein Homomorphismus ist, dass also
f([u][v]) = f([u]) f([v])
ist.
Ein anderes Problem?
Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos