Geschrieben von UntalentierterLogiker am 25.06.2010 um 19:46:
Syntaktische Monoide, Erkennbarkeit und Regularität
Meine Frage:
Syntaktische Monoide, Erkennbarkeit und Regularität I
Sei
eine Sprache und M ein endliches Monoid, das die Sprache L via eines Homomorphismus
erkennt.
Ohne Einschränkung (Warum?). Sei
surjektiv. Zeigen Sie, dass es einen surjektiven Homomorphismus
gibt. Folgern Sie, dass
das kleinste Monoid ist, das L erkennt
und dass insbesondere das syntaktische Monoid einer erkennbaren Sprache
endlich ist.
Meine Ideen:
Es ist
(Also bildet
auf die Äquivalenzklassen eines DFA ab)
(Soll ich ja zeigen)
Und
Also muss ich zeigen...
(Das wäre ja dann praktisch mein
)
Ich weiss jetzt nur nicht, wie ich das zeige. Vielleicht könnte ich zeigen, dass die Verkettung von
und
gleich
ist?
ist ja surjektiv...und aus der Surjektivität der Komposition zweier Abbildungsfunktionen
folgt ja, dass
surjektiv ist. Somit steht ja schonmal fest, dass
surjektiv ist, nicht?. Wie zeige ich nun, dass
richtig auf
abbildet?
Über einen kleinen Denkanstoß würde ich mich sseeehr freuen!
Danke im Voraus!
Grüße
UntalentierterLogiker