Syntaktische Monoide, Erkennbarkeit und Regularität

25.06.2010, 19:46	Auf diesen Beitrag antworten »
UntalentierterLogiker	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 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 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 abbildet? Über einen kleinen Denkanstoß würde ich mich sseeehr freuen! Danke im Voraus! Grüße UntalentierterLogiker


05.07.2010, 14:47	Auf diesen Beitrag antworten »
MSVler	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

Verwandte Themen