Informatiker Board | Druckvorschau: Syntaktische Monoide, Erkennbarkeit und Regularität

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 $[latex]L\subseteq \Sigma^*[/latex]$ eine Sprache und M ein endliches Monoid, das die Sprache L via eines Homomorphismus $[latex]\phi\colon\Sigma^*\to M[/latex]$ erkennt.
Ohne Einschränkung (Warum?). Sei $[latex]\phi[/latex]$ surjektiv. Zeigen Sie, dass es einen surjektiven Homomorphismus
$[latex]M \to Synt(L)[/latex]$
gibt. Folgern Sie, dass [latex]Synt(L)[/latex]

das kleinste Monoid ist, das L erkennt
und dass insbesondere das syntaktische Monoid einer erkennbaren Sprache
endlich ist.

Meine Ideen:
Es ist
$[latex]\phi \colon \Sigma^* \to M \to Synt(L)[/latex]$
$[latex]\pi \colon \Sigma^* \to \Sigma^*/ \equiv_L[/latex]$ (Also bildet $[latex]\phi[/latex]$ auf die Äquivalenzklassen eines DFA ab)
$[latex]\exists \delta \colon (\delta \colon M \to \Sigma^*/ \equiv_L )[/latex]$ (Soll ich ja zeigen)
Und
$[latex]\Sigma^*/ \equiv_L = Synt(L)[/latex]$
Also muss ich zeigen...
$[latex]\phi (w_1) = \phi (w_2) \quad \to \quad \pi (w_1) = \pi (w_2) \qquad,wobei \quad w_1,w_2 \in \Sigma^*[/latex]$
(Das wäre ja dann praktisch mein $[latex]\delta[/latex]$ )

Ich weiss jetzt nur nicht, wie ich das zeige. Vielleicht könnte ich zeigen, dass die Verkettung von $[latex]\phi[/latex]$ und $[latex]\delta[/latex]$ gleich $[latex]\pi[/latex]$ ist? $[latex]\delta[/latex]$ ist ja surjektiv...und aus der Surjektivität der Komposition zweier Abbildungsfunktionen $[latex]a\circ b[/latex]$ folgt ja, dass [latex]a[/latex]

surjektiv ist. Somit steht ja schonmal fest, dass $[latex]\phi \circ \delta[/latex]$ surjektiv ist, nicht?. Wie zeige ich nun, dass $[latex]w \in \Sigma^*[/latex]$ richtig auf [latex]Synt(L)[/latex]

abbildet?

Über einen kleinen Denkanstoß würde ich mich sseeehr freuen!
Danke im Voraus!

Grüße
UntalentierterLogiker