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

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

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 2 Beiträge
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
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