Formale Sprachen: Beweise mit Homomorphismus

Question

Frage:

Sei f : A*→ A* eine beliebige Funktion mit den in der jeweiligen
Teilaufgabe spezifizierten Eigenschaften. Ist f (im Allgemeinen) ein Homomorphismus?
Ist f ε-frei im Sinne der Aufgabe? Beantworten und beweisen Sie jeweils beide Fragen.
b) f (w) = ε, für alle w ∈ A*
c) f (x) = x, mit x ∈ A und |f (w)|= |w|, für alle w ∈ A*
d) für alle Teilworte lmr von w gilt: f (lmr) = f (l) · f (m) · f (r) für alle l, m, r ∈ A ∪{ε},
und alle w ∈ A*

Wie soll man da vorgehen? Danke!

Answer 1

1. Denk dir ein Alphabet \(A\) aus.
2. Denk dir eine Abbildung \(f\) aus, die die in der jeweiligen Teilaufgabe spezifizierten Eigenschaften hat.
3. Denk dir zwei Wörter \(w_1,w_2 \in A^*\) aus.
4. Prüfe ob \(f(w_1w_2) = f(w_1)f(w_2)\) ist. Falls nicht, dann ist \(f\) kein Homomorphismus. Falls doch, dann hat du mehrere Möglichkeiten:
   
   • gehe zurück zu 3. oder
     
   • gehe zurück zu 2. oder
     
   • gehe zurück zu 1. oder
     
   • beweise dass für jedes \(A\) jedes \(f\), dass die in der jeweiligen Teilaufgabe spezifizierten Eigenschaften erfüllt, ein Homomorphismus ist.