Diskussion:Kleenesche und positive Hülle

Artikelname

Da der Artikel sowohl die Kleenesche als auch die positive Hülle eines Alphabets/einer formalen Sprache behandelt und beide Operatoren aufgrund der Ähnlichkeit ihrer Definition sinnvollerweise nicht in getrennten Artikeln erklärt werden sollten, schlage ich vor, diesen Artikel zukünftig unter dem Lemma Kleenesche und positive Hülle zu führen. Gibt es Einwände gegen diesen Vorschlag? --Stephan Kulla 11:03, 21. Mär. 2008 (CET)

Da niemand Einwände gegen den Vorschlag erhoben hat, hab ich die Verschiebung des Artikels vorgenommen. --Stephan Kulla 15:16, 24. Apr. 2008 (CEST)

Gegenbeispiel

Kann jemand ein Beispiel einer Sprache geben, die über dem Kleene Operator (insb. Epsilon) nicht abgeschlossen ist? Das klingt alles so trivial, dass ich aus dem Artikel nicht herauslesen kann, wofür man das brauchen können soll bzw. warum das so ausführlich entwickelt wurde. --F GX 17:38, 5. Jun. 2009 (CEST)

Es ist ein Hüllenoperator, warum sollte es ein Gegenbeispiel geben? --Zahnradzacken 09:51, 3. Jan. 2012 (CET)

bezüglich dem dem Kleene Operator abgeschlossen zu sein macht für eine Sprache keinen Sinn (höchstens für eine Menge von Sprachen). Meintest du vieleicht eine Sprache L mit L* ungleich L? Da kannst du zum Beispiel die leere Sprache L={} nehmen... (nicht signierter Beitrag von 31.24.13.29 (Diskussion) 11:50, 2. Apr. 2013 (CEST))

Merkmale - vermutlich falsche Formulierung

Ich glaube es ist ein Formulierungsfehler im Absatz "Merkmale": 'Wenn eine Sprache L das leere Wort enthält, sind die Kleenesche und die positive Hülle beider Sprachen identisch und umgekehrt' - im ersten Teilsatz ist von 'einer' Sprache die Rede, um zweiten dann von Hüllen 'beider' Sprachen. Ich glaube das hier wäre korrekter: 'Wenn eine Sprache L das leere Wort enthält, sind die Kleenesche und die positive Hülle der Sprache identisch und umgekehrt' - ist das korrekt? --Prauch 11:12, 29. Dez. 2009 (CET)

Ja. Hat nur leider etwas gedauert, bis es korrigiert wurde. --Zahnradzacken 09:44, 3. Jan. 2012 (CET)

Ähnlichkeit zum Kartesisches Produkt

Die Menge von Wörtern der Länge <=n ergibt sich doch als n-faches Kartesisches Produkt eines Alphabets mit sich selbst? Wenn das stimmt, ab in den Artikel!--92.203.91.145 14:01, 2. Jan. 2012 (CET)

$\Sigma ^{n}\;{\xcancel {=\Sigma \times \ldots \times \Sigma }}$ (n-mal) ist einfach nur die Menge aller Wörter der Länge n (und nicht <= n). Der Zeichensatz bleibt $\Sigma$. --Zahnradzacken 15:11, 2. Jan. 2012 (CET)

Ist ε als leeres Zeichen nicht in jedem Alphabet enthalten? Wird ein Wort der Länge n, das auf ε endet nicht zu einem Wort der Länge n-1?--92.203.91.145 21:43, 2. Jan. 2012 (CET)

Nein, ε als Leeres Wort ist in keinem Alphabet enthalten. Die Länge von ε ist 0, deshalb ist ein Wort der Länge n ein Wort der Länge n+0 (und der Länge n+0+0....) und jedes Wort endet auf ε und endet auf εε ...

Ist ε in einem Alphabet vorhanden, so hat es nicht die Sonderrolle des leeren Worts inne und damit nicht die Länge 0 und die anderen Besonderheiten. --Zahnradzacken 09:33, 3. Jan. 2012 (CET)

Ok, du hast vollkommen recht! Aber dann kann man doch zumindest sagen, dass $\bigcup _{i=0}^{i=n}\Sigma ^{i}:=\bigcup _{i=0}^{i=n}\Sigma \ \times \ldots \times \Sigma$ die Menge von Wörtern der Länge <=n ist und damit eine Teilmenge von $\Sigma ^{*}$. Wenn das stimmt, sollte es imho in den Artikel.--92.203.3.132 15:09, 4. Jan. 2012 (CET)

<= stimmt nicht, $\Sigma ^{n}$ sind Wörter der Länge "genau n", nicht kürzer, nicht länger. Dass diese Wörter eine Teilmenge aller Wörter über $\Sigma$ sind, stimmt. Sieht für mich aber sehr trivial aus, weil es aus der Definition folgt: man vereinigt die Mengen $\Sigma ^{n}$, da ist klar, dass jede dieser Mengen Teilmenge der Vereinigung ist. Falls du das nicht trivial findest, oder aber für dich die Deutung der Definition ("Die Menge der Wörter der Länge n über einem Alphabet ist eine Teilmenge der Menge aller Wörter über diesem Alphabet") nicht auf der Hand liegt, dann schlag doch kurz vor, wo man das am besten unterbringt. --Zahnradzacken 18:38, 4. Jan. 2012 (CET)

ich vereinige ja die Mengen deswegen <= (vereinigungsmenge der Wörter der Länge i, wobei i von 0 bis n läuft...) deswegen stimmt imho das <= jetzt. Du hast aber recht, dass ich es vorher falsch geschrieben habe (jetzt korrigiert). Dass es sich um eine Teilmenge handelt ist wohl trivial! Ich meine eher die Sache mit dem Kartesisches Produkt, diese Verbindung liegt wohl früher oder später auf der Hand, aber ich finde man sollte sie einbauen, weil es doch ein bekanntes mathematisches Instrument ist. Man sollte vielleich schreiben: $\Sigma ^{*}=\bigcup _{i\in \mathbb {N} }\Sigma ^{i}$ vereinigt mit {ε}, wobei epsilon das leere Wort ist und $\Sigma ^{i}$ das i-fache karthesische Produkt.--92.203.121.165 10:41, 6. Jan. 2012 (CET)

Habe es jetzt in den Artikel eingebaut.

Nachdem du die Formel korrigiert hast, sehe ich, worauf du hinaus wolltest. Da war mein Blick etwas verstellt. Deine Formulierung im Artikel hat auch reichlich Bezug zum Lemma, ist hier also erhellend. Ich musste aber auch nochmal nachlesen, um mir Folgendes klar zu machen:$\Sigma ^{n}$ ist nicht durch das Kreuzprodukt definiert. Man könnte das zwar machen, müsste dann aber den Tupeln aus $\Sigma \times \cdots \times \Sigma$ noch eine Bedeutung geben. Also definiert man einfach lieber direkt für $\Sigma ^{n}$ die Bedeutung mittels $\Sigma ^{*}$: $\Sigma ^{i}=\{w\mid w\in \Sigma ^{*}\land \left|w\right|=i\}$. --Zahnradzacken 17:37, 7. Jan. 2012 (CET)

IMHO ist folgendes anzuwenden: "Die Konkatenation ist eine Abwandlung der Produktmengen-Operation (kartesisches Produkt) unter Vernachlässigung der Tupel-Schreibweise." aus Konkatenation (Mengen). Damit ist eine Definition mit dem kartesischen Produkt (und Vernachlässigung der Tupelschreibweise) äquivalent zu der in der Informatik.--biggerj1 12:29, 8. Jan. 2012 (CET)

Die Vernachlässigung der Tupel-Schreibweise finde ich falsch und diese Formulierung habe ich entfernt. Sie ist keine Voraussetzung für die Konkatenation, eine Schreibweise ist nicht Teil der Definition. Das Beispiel im Artikel Wort (Theoretische Informatik) zeigt außerdem, dass man die Tupel-Schreibweise manchmal benötigt. Den Bezug zum Kreuzprodukt habe ich auch entfernt, das müsste man schon klarer ausdrücken als mit "steht dem nahe".

Es bleibt die Frage, ob $\Sigma \circ \Sigma =\Sigma ^{2}$ ist, wenn $\Sigma ^{2}$ durch $\Sigma ^{*}$ definiert wird. Die linke Seite setzt voraus, dass man Buchstaben mit Buchstaben konkatenieren kann. Die rechte Seite kann als Konkatenation eine Funktion haben, die nur Wörter mit Buchstaben konkateniert. Wie würdest du mit der Definition der linken Seite das leere Wort definieren? --Zahnradzacken 16:10, 8. Jan. 2012 (CET)

Ja,ist es, weil es alle Wörter der Länge 2 enthält. Bei dir und bei mir ist das leere Wort ausgeschlossen. Bemerke, dass du das leere Wort ebenfalls nicht neu definierst, sondern auf die Definition zurückgreifst, dass es die Länge 0 hat. Das leere Wort kann man damit nicht definieren, da es nicht im Alphabet auftritt. Es ist ein eigenständiges Wort. $\Sigma ^{*}$ wird dann dadurch definiert, dass es die Vereinigung von $\Sigma ^{+}$ mit der Menge, die nur das leere Wort enthält ist. Das leere Wort muss eigenständig definiert werden. Ich werde den Bezug nicht mehr einbauen, auch wenn ich ihn für sehr interessant halte. Wenn dann mach du es, nachdem du meinen Beitrag ja revertiert hast. Bem.: Du schreibst Kreuzprodukt- du meinst aber das kartesische Produkt. IMHO handelt es sich bei der Verwendung oder Vernachlässigung der Tupelschreibweise nur um die in Konkatenation (Mengen) ausgeführte Konvention bezüglich des Kartesischen Produktes. Du solltest auch berücksichtigen, dass ich nur $\Sigma ^{+}$ über das Kartesische Produkt definiert habe, dort benötigt man das leere Wort nicht, da es ausgeschlossen ist (siehe Artikel). --biggerj1 17:03, 8. Jan. 2012 (CET)

@Biggerj1. Wir können uns auch einfach zunächst einigen, bevor wir irgendeinen Gegenstand der Diskussion in den Artikel schreiben. Verzeihung, falls du dich "revertiert" fühltest, ich habe deine Ergänzung nur auf das gekürzt, was neu war. Die Frage der Gleichheit oben habe ich mir gestellt, weil mir nicht klar war, ob Tupel endlichen Folgen gleichzusetzen sind. Wenn man sich die Diskussion:Tupel ansieht, ist das wohl auch eine heiß diskutierte Angelegenheit. @Daniel5ko, willst du hier etwas dazu sagen?

Ich kann gut damit leben, Tupel und Folgen in diesem Feld als gleich zu betrachten. Nimmt man noch Assoziativität des kartesischen Produkts an, braucht man aber gar nicht den Umweg über die allgemeinere Mengenkonkatenation, das kartesische Produkt (auch "Kreuzprodukt" genannt "kreuzprodukt"+mengen) reicht dann vollkommen.

Die Frage nach dem leeren Wort war etwas davon losgelöst: Wenn $\Sigma \circ \Sigma =\Sigma \times \Sigma$ eine Sprache ist, man also mit dem kartesischen Produkt von Alphabeten Sprachen definiert, möchte man auch ein leeres Wort. Könnten wir das leere Wort nicht mit dem kartesischen Produkt ausdrücken, wäre diese Wahl wohl nicht die richtige gewesen, denn bei endlichen Folgen wird das leere Wort nicht eigenständig definiert, es ist tatsächlich innerhalb der Menge der endlichen Folgen jene mit Länge 0. Es gibt aber zum Glück das 0-Tupel, also haben wir hier schon das leere Wort.

Falls du einverstanden bist, kann man im Artikel Mengenkonkatenation durch Kartesisches Produkt ersetzen und damit auch $\Sigma ^{*}$ definieren. --Zahnradzacken 20:56, 8. Jan. 2012 (CET)

Entschuldige meine Wortwahl, die war oben wohl etwas ruppig :(!!! Ich entschuldige mich hiermit bei dir dafür!!!! Ich vertrete diese Auffassung: http://www.encyclopediaofmath.org/index.php/Tuple .Siehe mitte bei den Synonymen. Dort heisst es dass

1. Tupel Folgen sind
2. Wörter Tupel sind
3. Tupel ein Element des n-Fachen kartesischen Produktes sind (wenn du nun die Tupelschreibweise vermeiden willst, lässt du einfach wie bei Konkatenation (Mengen) die Klammern und Kommas weg)
4. ...

Assoziativität bei Kartesischen Produkt "besteht" ja bis auf eine Notationsänderung Kartesisches_Produkt#Assoziativgesetz. Werden die Klammern weggelassen, wie bei Konkatenation (Mengen) hat man automatisch ganz saubere Assoziativität. Von daher baue die Änderungen mal ein, wie du sie meinst.

--biggerj1 21:36, 8. Jan. 2012 (CET)

Ich fand die Diskussion eigentlich beiderseits sachlich, also deine Entschuldigung war nicht nötig :)

Das mit der Assoziativität sehe ich zwar etwas anders (Klammern weglassen bringt einem nicht die Assoziativität – es läuft anders herum), aber die kanonische Bijektion muss man nicht unbedingt im Artikel erwähnen, hat mit dem Thema hier dann schon recht wenig zu tun. --Zahnradzacken 23:18, 8. Jan. 2012 (CET)

Hmm, man kann Assoziativitätsproblematik auch umgehen, indem man sagt: Elemente von $\Sigma ^{*}$ sind einfach Paare $(n,f)$ mit $n\in \mathbb {N}$ und $f\colon n\to \Sigma$ (hier ist $n$ von-Neumann-Numeral). Alle Bits sind effektiv ausgenutzt, und man hat keinen Informationsüberschuss in der Kodierung durch eventuelle Tupelklammerung. Auch sieht man dann zum Beispiel den Unterschied zwischen $\Sigma$ und $\{\alpha \in \Sigma ^{*}\mid |\alpha |=1\}$ mal ganz gut. --Daniel5Ko 00:17, 9. Jan. 2012 (CET)

Schön, dass hier fleissig diskutiert wird. Ich will nur mal anmerken, dass es mir hauptsächlich um die Ähnlichkeit mit dem Kartesischen Produkt ging. Biggerj1 hat ja sogar eine Quelle dafür gefunden http://www.encyclopediaofmath.org/index.php/Tuple . Dort heisst es explizit: "a word in the alphabet" ist ein Synonym zu "Tupel". Worauf warten, einbauen! Bzw.: "an element of some Cartesian power of the set X" ist ein Tupel, also zusammen (da beide Synonyme sind): "a word in the alphabet is an element of some Cartesian power of the set X". Meiner Meinung nach ist die Diskussion hiermit beendet, da eine Quelle gefunden wurde. Siehe auch englische Wikipedia!--92.203.33.173 16:34, 9. Jan. 2012 (CET)

Schön, dass deiner Meinung nach die Diskussion beendet ist. Das rechtfertigt nicht, dass du die Diskussionspunkte ignorierst. Wenn in einer Quelle Tupel durch das Kreuzprodukt definiert werden, sind dadurch die anderen Definitionen nicht falsch. Wie Daniel5Ko schreibt, kann man Tupel auch anders definieren, zum Beispiel als Folgen (ohne eine Definition von "Tupeln" zu benötigen). Wort und Tupel sind also nicht immer synonym. Die Mengenkonkatenation als Abwandlung des Produkts "unter Vernachlässigung" der Tupelschreibweise zu "definieren", kann man so jedenfalls nicht in den Artikel schreiben. Das steht zwar so im Artikel Konkatenation (Mengen), aber belegt wird das nicht. Es klingt ziemlich blödsinnig. Wie kann eine Definition über eine Schreibweise definiert werden? Es wird dort außerdem behauptet, "in aller Regel" werde die Listenkonkatenation benutzt. Was "Listen" sind, ist aber wieder nicht definiert. Sind es Tupel, sind es Folgen? Wenn Wörter Listen sind, dann ist diese Definition gleichbedeutend zur Konkatenation von Sprachen (Formale Sprache#Konkatenation). Da für diesen Artikel die Mengen aus Wörtern und deren Verknüpfung die Wort (Theoretische Informatik)#Konkatenation ist, ist das eigentlich gar keine alternative Definition:

• Ein Wort ist ein Tupel der Länge n aus Sigma.
• Die Konkatenation zweier Wörter ist definiert.
• Die Konkatenation von Mengen von Wörtern ist definiert. Sigma ist aber keine Menge von Wörtern, also ist darauf keine Konkatenation definiert.

Ich bin deshalb dafür, dass der Verweis auf Konkatenation (Mengen) gestrichen wird. Die Definition als kartesisches Produkt geht in Ordnung. --Zahnradzacken 14:18, 16. Jan. 2012 (CET)

Das ist doch aber ein sehr verwandter Ansatzpunkt. Von mir aus lösche alles ohne Quellen, aber das was Quellen hat, solltest du drin lassen. So sagt z.B. das eine Buch, dass Wörter sogar über das Kartesische Produkt definiert werden - wo man imho das Problem mit der Tupelschreibweise hat - Darauf geht das andere Buch ein und bestätigt, dass dabei ein formales Problem besteht. IMHO ist genau dafür die "Konkatenation (Mengen)" die Lösung. Deswegen habe ich der Diskussion auch den Namen "Ähnlichkeit zum kartesischen Produkt" gegeben. Diese Ähnlichkeit liegt wohl unbestritten vor, aber ich widerhole mich. Dafür, wofür es Quellen gibt, drin lassen und schau bitte vorher nach bevor du löschst ;) --92.203.60.114 17:00, 17. Jan. 2012 (CET)

Ich habe bisher kaum mehr als Doppeltes und den vagen Satz über die "Tupelschreibweise" entfernt. Beim Löschen habe ich den von dir gewünschten Bezug ("Ähnlichkeit") zur Mengenkonkatenation erhalten.

Worin siehst du das Problem mit der Tupelschreibweise? Das kartesische Produkt ist (anders als in deinen Quellen) nicht nur für Mengenpaare definiert – es gibt auch eine verallgemeinerte Variante (siehe den WP-Artikel und [1]). Darum sehe ich darin kein formales Problem. Man sollte es natürlich nicht auf Sprachen anwenden, sondern schon auf Alphabete, worüber wir hier ja reden. Von welchen beiden Büchern sprichst du eigentlich, du hast doch nur eins angegeben: ein Datenbankbuch, das sich meiner Meinung nicht gerade als Quelle zur Klärung von Feinheiten bei formalen Sprachen eignet (schon, weil es einfach nur die Konkatenation von Sprachen beschreibt, nicht die von Alphabeten). Das eigentliche Problem habe ich mit dem kartesischen Produkt, weil es davon auch wieder mehrere Definitionen gibt, wie schon der oben verlinkte Eintrag auf Encyclopedia of Mathematics zeigt. Mal als Menge von Funktionen, mal induktiv. Bei der dort angegebenen induktiven Definition wäre $\Sigma ^{1}=\Sigma$, anders als wenn man die Definition als Menge von Funktionen betrachtet.

Die von dir bevorzugte Konkatenation von Mengen muss man sich auch erst zurecht biegen. Welche Verknüpfung muss man denn verwenden, damit die i-fache Konkatenation von Alphabeten funktioniert? Und wie ist die i-fache Konkatenation definiert? --Zahnradzacken 20:42, 17. Jan. 2012 (CET)

Vielleicht sollten wir uns einfach auf die Quellen beziehen, um die Diskussion nicht weiter ausufern zu lassen ;) Hier ist noch das andere angegebene Buch. Hier wird explizit der Bezug zum kartesischen Produkt hergestellt: http://books.google.de/books?id=KWdpmtxIPpEC&lpg=PP1&hl=de&pg=PA27#v=onepage&q&f=false (Inhalt: Wort der Länge i --> kartesisches Produkt) . Ich habe zwar meine Bedenken, die hier auch geteilt werden: http://books.google.de/books?id=_Z0DTXSJHfwC&lpg=PP1&hl=de&pg=PA137#v=onepage&q&f=false (Zitat: "Man beachte, dass die Konkatenation formal nich dasselbe Ergebnis liefert wie das kartesische Produkt...") . Es wird dort jedoch auch gesagt, dass sich das Ergebnis nur formal unterscheidet, die Unterscheidung z.B. bei SQL nicht getroffen wird. IMHO liegt der Unterschied in der Tupelschreibweise ^{Quelle benötigt} (die mit Klammerung einhergeht), welche in der Konkatenation (Mengen) sowieso vernachlässigt wird (laut WP-Artikel) ^{Quelle benötigt}. Siehst du noch andere Probleme?. Sei mutig. Ein Satz, der auf das kartesische Produkt verweist reicht mir. dann bin ich schon zufrieden. Ich habe aus dem Buch hier http://books.google.de/books?id=KWdpmtxIPpEC&lpg=PP1&hl=de&pg=PA27#v=onepage&q&f=false nur noch die Konvention $\Sigma ^{0}=\{\varepsilon \}$ übernommen, damit $\Sigma ^{*}$ definiert werden kann. Von mir aus kick den Rest meiner letzten Änderung, aber lass den Verweis auf das Buch als Quelle und den Hinweis auf die Konvention.--92.203.60.114 21:07, 17. Jan. 2012 (CET)

Quellen allein helfen hier auch nicht weiter, weil man sich die Definitionen nicht so gut aus verschiedenen Quellen zusammensuchen kann. Die folgenden Bücher "belegen" die Verwendung des kartesischen Produkts zur Bildung von Sprachen: [2], [3]. Dieses Buch definiert die Kleenesche Hülle induktiv und Sprachen als Teilmengen der Kleeneschen Hülle.

Du verwechselst dagegen immer noch das kartesische Produkt von Alphabeten mit der Konkatenation von Sprachen. Das Buch, dass deine "formalen Bedenken" teilt, ist da vielleicht mit dran schuld. Es spricht von einer "Analogie" zu formalen Sprachen, aber es konkateniert Relationen. Aber nirgends ist die Rede davon, das kartesische Produkt als alternative Definition zur Konkatenation von Sprachen zu verwenden. Du verwechselst leider auch weiterhin Konvention und Definition. Vielleicht wirst du mit meinen Änderungen trotzdem einverstanden sein. --Zahnradzacken 03:23, 19. Jan. 2012 (CET)

Vielen Dank :) --92.203.18.241 16:10, 20. Jan. 2012 (CET)

Dieser Abschnitt kann archiviert werden. --92.203.47.98 19:49, 6. Apr. 2012 (CEST)

Merkmale

Die Kleensche Hülle einer Sprache ist nur dann abzählbar, wenn die Sprache selbst schon abzählbar ist. (nicht signierter Beitrag von 91.190.9.210 (Diskussion) 16:10, 28. Mär. 2013 (CET))

Fragezeichenoperator

Was mit dem Fragezeichenoperator? Also wenn das Wort nur kein mal oder ein mal vorkommt?--Albin Schmitt (Diskussion) 18:08, 13. Mär. 2020 (CET)