0 Daumen
110 Aufrufe

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

von

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.

1 Antwort

+2 Daumen
 
Beste Antwort

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.

von  –  ❤ Bedanken per Paypal

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...