Diskussion:Ω-reguläre Sprache

Definition

Was ist bei der Definition mit $U^{\omega }\cdot L_{1}$ gemeint? Eine Konkatenation zweier $\omega$-Sprachen ist mir so nicht bekannt. Ich denke aber, auch mit Hinblick auf die Tatsache, dass daraus alle $\omega$-regulären Sprachen entstehen sollen, dieser Punkt ist falsch. Ich vermute es sollte heißen $U^{*}\cdot L_{1}$ wobei mit $U^{*}$ der Kleene-Abschluss gemeint ist. --Redmaniac 09:07, 10. Jan. 2009 (CET)

da hat sich ja tatsächlich der fehlerteufel eingeschlichen. die zweite konstruktionsvorschrift ist: wort aus regulärer sprache konkateniert mit wort aus omega-regulärer sprache - ist ja eigentlich nachvollziehbar und steht im englischen artikel auch genau so drin. ich ändere das gleich mal. gruß --Murkel ^(anmurkeln) 23:03, 10. Jan. 2009 (CET)

Verständlichkeit

Für nicht-Informatiker absolut unverständlich, von Omma-Test will ich gar nicht erst reden --WolfgangS 19:14, 11. Apr. 2007 (CEST)

Zwar stimme ich zu, das man versuchen sollte Artikel so verständlich wie möglich zu schreiben, aber ich halte diesen Kritikpunkt für nicht ganz zutreffend: Dieser Artikel zählt nicht zu den Grundlagen der Informatik. Man braucht schon etwas Vorwissen aus anderen Teilgebieten der Mathematik und Informatik bevor man mit diesem Thema überhaupt etwas anfangen kann. Daraus ergibt sich, dass ein Artikel zu diesem Thema entweder nahezu inhaltsleer ist (dafür aber verständlich) oder aber fachlich korrekte Informationen enthält, die dann nicht mehr jedem zugänglich sind (ohne Vorwissen).

Da die Wikipedia auch von Fachleuten genutzt wird, die Informationen benötigen, welche über den intuitiven und leicht verständlichen Rahmen hinausgehen, halte ich es für legitim komplexere Inhalte auch im ensprechenden Format anzubieten. --Redmaniac 21:51, 3. Jan. 2009 (CET)

Zusammenhang zwischen $\omega$-regulären Sprachen und $\omega$-Automaten

Ich habe den letzen Satz gestrichen: "Damit ist jede Sprache, die von einem ω-Automaten akzeptiert wird, ω-regulär. Aber nicht jede ω-reguläre Sprache wird von einem ω-Automaten akzeptiert"

Diesen Satz finde ich unglücklich gewählt: Eine Sprache ist $\omega$-regulär genau dann, wenn die Büchi-Erkennbar ist. Es ist aber dann irreführend (bzw. falsch) zu sagen, dass nicht jede $\omega$-reguläre Sprache von einem $\omega$-Automaten erkannt wird. Das stimmt etwa für deterministische Büchi Automaten, die eine echte Teilklasse der $\omega$-regulären Sprachen erkennen. Aber es gilt eben nicht für alle $\omega$-Automaten. Man könnte sogar so weit gehen zu sagen, dass diese Aussage schlicht falsch ist, da es für jede $\omega$-reguläre Sprache immer einen $\omega$-Automaten (nämlich einen nichtdeterminstischen Büchi-Automaten) gibt, der die Sprache erkennt.

Im übrigen ergibt sich die Aussage nicht aus dem vorangehenden Text, weshalb es irreführend ist den Satz mit "Damit ..." einzuleiten. --Redmaniac 17:22, 3. Jan. 2009 (CET)

In meine Neubearbeitung habe ich ausschließlich den Zusammenhang mit Büchi-Automaten übernommen, denn nach einer kurzen Lektüre von ω-Automat war mir nicht klar, warum jeder dieser Automaten in seinem Akzeptanzverhalten zu einem Büchi-Automaten äquivalent sein sollte. Bei Bedarf kann der Satz aber natürlich nachgetragen werden.

--86.56.98.22 01:35, 7. Aug. 2012 (CEST)

Hast du für deine Überarbeitung Literatur verwendet? Es wäre nämlich schön, wenn welche im Artikel ergänzt werden würde. Außerdem habe ich eine Frage zu deiner Änderung. Sie erscheint mir genauer zu sein, als die alte Version, aber fehlt nicht noch die Definition von $U^{\omega }$, weil $\cdot ^{\omega }$ bisher nur für Alphabete definiert wurde? Und ist auch die leere Menge als Teilmenge von $\Sigma ^{\omega }$ eine $\omega$-Sprache? --Zahnradzacken (Diskussion) 12:00, 7. Aug. 2012 (CEST)

Abgesehen von der Quelle im englischen Artikel kann ich nur ein VL-Skriptum [1] anbieten, das sich aber auch nur grob mit Büchi-Automaten im Zusammenhang mit LTL bschäftigt und auf den Begriff ω-reguläre Sprache überhaupt nicht eingeht (daher auch nicht als Quelle angegeben). Zu deiner Frage, im Abschnitt Definition wird $U^{\omega }$ als abzählbare Konkatenation von Worten aus $U$ erklärt, wenn auch vielleicht nicht explizit definiert. M.M.n. ist das ausreichend, zumindest wenn der LeserIn bekannt ist, wie Konkatenation bzw. die Potenz einer Sprache erklärt ist. Alternativ kann mensch $U^{\omega }=U^{\mathbb {N} }$ auch wieder als Funktionenraum definieren.

Die Ungenauigkeit der Definition hat mich auch erst dazu gebracht den Artikel zu bearbeiten, denn die alte Version hat nicht ausgeschlossen, dass das leere Wort in einer ω-reguläre Sprache enthalten ist. Die leere Sprache im Übrigen auf jeden Fall eine ω-Sprache und sogar ω-regulär (wähle dazu $U$ leer). Der "springende Punkt" ist, wenn überhaupt ein Wort in einer ω-Sprache enthalten ist, dann muss es unendlich lang sein.

LG. --86.56.98.22 21:15, 8. Aug. 2012 (CEST)

Ja, danke auch nochmal für die Verbesserung. Ich finde nur, dass die "Definition" sich nicht unbedingt in der rekursiven Definition von $\omega$-regulär verstecken sollte. Neben der Definition in der Definition erschwert auch das Wort "abzählbar" das Verständnis, wegen der Mehrdeutigkeit wie in Abzählbarkeit beschrieben. Habe es deswegen etwas abgeändert. Gruß --Zahnradzacken (Diskussion) 23:54, 8. Aug. 2012 (CEST)

Stimmt, du hast recht "abzählbar" alleine war mehrdeutig, besten Dank! --86.56.98.22 00:30, 9. Aug. 2012 (CEST)

Menge aller Abbildungen

"Sei $\Sigma$ ein Alphabet, dann ist die Menge $\Sigma ^{\omega }$ aller unendlichen Wörter über $\Sigma$ definiert als die Menge aller Abbildungen von $\mathbb {N}$ nach $\Sigma$."

$\Sigma ^{\omega }$ ist einerseits eine "Menge an Wörtern", andererseits eine "Menge von Abbildungen"? Da stimmt etwas nicht. Gemeint wäre wahrscheinlich eher die Menge aller Bilder.

--141.23.185.201 13:02, 21. Dez. 2023 (CET)