Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Reguläre Sprachen, Erkennbarkeit, Transitionsmonoide
Autor
Universität/Hochschule J Reguläre Sprachen, Erkennbarkeit, Transitionsmonoide
elias114
Neu Letzter Besuch: im letzten Monat
Dabei seit: 15.09.2021
Mitteilungen: 3
  Themenstart: 2021-09-20 09:29

\(\begingroup\)\(\newcommand{\N}{\mathbb{N}}\) Liebes Forum, zur Übung bin ich gerade am Verstehen eines Beweises des Satzes, dass eine Sprache genau dann regulär ist, wenn sie erkennbar ist. (Erkennbar ist eine Sprache genau dann, wenn ein endliches Monoid $M$ und ein Homomorphismus $\varphi: \Sigma^* \to M$ existieren mit $\varphi^{-1}(\varphi(L)) = L$). Für die eine Richtung ("$\Longrightarrow$") benötigt man noch das Transitionsmonoid für einen gegebenen DEA $M := (Q, \Sigma, \delta, q_0, F)$. Eine Transition für ein festes $w \in \Sigma^*$ ist eine Abbildung $t_w: Q \to Q, q \mapsto \delta(q, w)$, sie bildet also einen Zustand auf ihren Folgezustand ab, wenn $w$ gelesen wird. Mit der Komposition als Verknüpfung und $t_{\varepsilon}$ als neutralem Element bildet es ein Monoid. (Bezeichnen wir hier einmal die Menge aller Transitionen von $M$ als $\mathbf T_M$.) Für den eigentlichen Beweis nehmen wir $(\mathbf T_M, \circ, t_{\varepsilon}$ als endliches Monoid (endlich, da es nur endlich viele Abbildungen von $Q$ nach $Q$ geben kann), und den Homomorphismus $\varphi: \Sigma^* \to \mathbf T_M, w \mapsto t_w$. Man sieht ein, dass $$\varphi(L) = \{t_w \mid w \in \Sigma^*, t_w \in \mathbf T_M, \hat{\delta}(q_0, w) \in F\} \subseteq \mathbf T_M$$ ist. Nun zu meiner eigentlichen Frage: Wieso ist $\varphi$ überhaupt ein Homomorphismus? Denn ich rechne: $$\varphi(w_1 \circ w_2) = \varphi(w_1w_2) = t_{w_1w_2} = t_{w_2} \circ t_{w_1} = \varphi(w_2) \circ \varphi(w_1),$$ was nicht $\varphi(w_1) \circ \varphi(w_2)$ ist. Das Vertauschen kommt daher: $$t_{w_1w_2}(z) = \hat{\delta}(z, w_1w_2) = \hat{\delta}(\hat{\delta}(z, w_1), w_2) = \hat{\delta}(t_{w_1}(z), w_2) = t_{w_2}(t_{w_1}(z)).$$ Macht ja auch Sinn, da ich ja zuerst den Folgezustand von $w_1$ und dann den von $w_2$ berechnen will. Wo liegt der Fehler? Danke für eure Antworten!\(\endgroup\)


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2182
  Beitrag No.1, eingetragen 2021-09-20 10:07

Hallo elias114, die Diskrepanz liegt daran, dass die Argumente der Funktionskomposition im Vergleich zu den Argumenten der Konkatenation einfach die "falsche" Reihenfolge haben. Das ist aber kein schwerwiegendes Problem, denn man kann für M ja festlegen, dass die Verknüpfung Funktionskomposition ist, nur eben mit vertauschten Argumenten.


   Profil
elias114
Neu Letzter Besuch: im letzten Monat
Dabei seit: 15.09.2021
Mitteilungen: 3
  Beitrag No.2, vom Themenstarter, eingetragen 2021-09-20 11:20

\(\begingroup\)\(\newcommand{\N}{\mathbb{N}}\) Das heißt, ich würde $(\circ): (t_{w_1}, t_{w_2}) \mapsto t_{w_2} \circ t_{w_1}$ definieren? Reicht das schon?\(\endgroup\)


   Profil
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 2182
  Beitrag No.3, eingetragen 2021-09-20 13:38

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\) Ja. Wobei es vielleicht etwas verwirrend ist, auf beiden Seiten $\circ$ zu benutzen. Besser ist vielleicht sowas wie $f \bullet g := g \circ f$ oder $f \circ g := x \mapsto g(f(x))$.\(\endgroup\)


   Profil
elias114
Neu Letzter Besuch: im letzten Monat
Dabei seit: 15.09.2021
Mitteilungen: 3
  Beitrag No.4, vom Themenstarter, eingetragen 2021-09-20 20:33

Alles klar, danke für die rasche Antwort!


   Profil
elias114 hat die Antworten auf ihre/seine Frage gesehen.
elias114 hat selbst das Ok-Häkchen gesetzt.
elias114 wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]