|
|
Syntaktische Monoide, Erkennbarkeit und Regularität |
|
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
|
|
25.06.2010 19:46 |
|
|
MSVler unregistriert
|
|
ohje fsa hausaufgaben im internet machen,
geb mal bei google "fsab-skript"
seite 15
grüße ein Msv'ler
// dachdecker2: die Löschanfrage zu deinem Post erreichte mich zu spät, ich will den Post von UntalentierterLogiker nicht mitlöschen, sorry
|
|
05.07.2010 14:47 |
|
|
|
|
|
|
|