Aufgabe:
Monoide und Sprachen
Zur Erinnerung: Ein Monoid ist eine Menge M mit einer binären Verknupfung ¨
◦ : M × M → M, (m, n) 7→ m ◦ n
welche die folgenden Eigenschaften besitzt:
Die Verknupfung ist assoziativ, d.h. f ¨ ur alle ¨ n, m, k ∈ M gilt:
(n ◦ m) ◦ k = n ◦ (m ◦ k).
Es gibt ein neutrales Element e ∈ M mit der Eigenschaft, dass fur alle ¨ m ∈ M
gilt:
e ◦ m = m = m ◦ e.
Bitte beachten Sie: Ist eine Verknupfung ¨ ◦ auf einer Menge M gegeben und Sie
möchten uberpr ¨ ufen, ob ¨ M mit dieser Verknupfung ein Monoid ist, so m ¨ ussen Sie ¨
unter anderem zeigen, dass fur alle ¨ m, n ∈ M gilt, dass m ◦ n ∈ M.
Wir schreiben (M, ◦, e) fur das Monoid ¨ M mit der Verknupfung ¨ ◦ und dem neutralen
Element e. Beachten Sie, dass ◦ und e lediglich Namen sind. Verknupfungen heißen ¨
oft z.B. ”·” oder ”+”, das neutrale Element wird häufig auch mit 1 oder 0 bezeichnet
(je nachdem, ob die Verknupfung multiplikativ oder additiv geschrieben wird). Wenn ¨
◦ und e klar sind werden diese zum Teil weggelassen.
Die Menge Σ∗ bildet mit der Kontakenation als Verknupfung und dem leeren Wort ¨
als neutralem Element ebenfalls ein Monoid. Das bedeutet, sind v, w ∈ Σ
∗
, so ist
v ◦ w = vw.
(a) Sei Σ ein endliches nicht-leeres Alphabet. Zeigen Sie:
i. Sei L ⊆ Σ
∗
, 2 ≤ |L| < ∞. Dann ist L kein Monoid.
ii. Es gibt genau eine Sprache L ⊆ Σ
∗ mit |L| = 1 und L ist ein Monoid.
iii. Es gibt eine reguläre Sprache L ( Σ
∗ mit |L| = ∞, welche ein Monoid ist.
Problem/Ansatz:
Hab bereits 5h damit verbracht mir videos und Informationen im Internet anzuschauen über Monoide aber kann einfach nix finden was mir zeigt oder erklärt was ich für diese Aufgabe hinzuschreiben habe. Freue mich über jede Hilfe
