Informatiker Board | formale Sprachen | Syntaktische Monoide, Erkennbarkeit und Regularität

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Syntaktische Monoide, Erkennbarkeit und Regularität

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Syntaktische Monoide, Erkennbarkeit und Regularität

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

UntalentierterLogiker
Grünschnabel

Dabei seit: 25.06.2010
Beiträge: 1

Syntaktische Monoide, Erkennbarkeit und Regularität

Zitatantwort auf diesen Beitrag erstellen

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

25.06.2010 19:46

Beiträge von UntalentierterLogiker suchen

Nehmen Sie UntalentierterLogiker in Ihre Freundesliste auf

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

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Syntaktische Monoide, Erkennbarkeit und Regularität