Diskussion:Bewertungsfunktion (Formale Sprachen)

Unverständlich

Der Unverständlichkeits-Baustein ist nicht zu Unrecht im Artikel. Mir ist Folgendes unklar:

1. Was ist $\Gamma$, was ist $Q$? Offensichtlich soll $\Sigma =\Gamma \cup Q$ gelten, aber das steht nicht da. Warum unterscheiden wir $\Gamma$ und $Q$?
2. Wie ist die Länge einer Grammatik (Abschnitt Motivation) definiert?

-- UKoch (Diskussion) 19:50, 27. Jan. 2013 (CET)

Warum da $\Gamma$ und $Q$ unterschieden werden, weiß ich auch nicht. Zur Definition einer "Bewertungsfunktion" ist das aber auch unwichtig. Ich schätze mal, das ist aus Zweikellerautomat eingeschleppt.

Die "Länge" der Grammatiken meint wahrscheinlich die Anzahl der Regeln. Ich kann da zwar nur raten, aber alles andere, was mir so einfällt, dürfte man unmöglich "Länge" nennen.

Allgemeine Gedanken: Daraus, dass $\Sigma ^{*}$ das freie Monoid über $\Sigma$ ist, ergibt sich automatisch eine 1-zu-1-Korrespondenz zwischen beliebigen Funktionen $h\colon \Sigma \to UM$ und Monoid-Homomorphismen $h^{*}\colon \Sigma ^{*}\to M$ ($M$ beliebiges Monoid, $U\colon \mathbf {Mon} \to \mathbf {Set}$ Vergissfunktor), die man im Fall von $M=(\mathbb {N} ,+)$ mit Addition ganz explizit hinschreiben kann und auch sollte. Die Definition von Monoid-Homomorphismen für den Spezialfall $M=(\mathbb {N} ,+)$ zu erwähnen, wie es gegenwärtig geschieht, ist dagegen nicht besonders sinnvoll.

--Daniel5Ko (Diskussion) 21:10, 7. Feb. 2013 (CET)

Zum 1. Punkt: OK, dann ersetze ich gleich $\Gamma \cup Q$ durch $\Sigma$.

Zum 2. Punkt: Ich habe auf WP schon mal (weiß leider nicht mehr, wo) die Größe einer Grammatik als die Summe der Längen beider Regelseiten definiert gesehen. Ergäbe das hier Sinn?

Zum 3. Punkt: Ich bin zwar ein relativ theoretisch ausgerichteter Informatiker, hatte aber mit Kategorientheorie nie was zu tun. Deine "allgemeinen Gedanken" überfordern mich darum. Sehe ich das richtig, dass Du dafür plädierst, die Definition der Monoid-Homomorphismen aus dem Artikel 'rauszunehmen? Oder sollte man auf die allg. Def. verweisen?

-- UKoch (Diskussion) 16:04, 8. Feb. 2013 (CET)

Zu Punkt 3: Ja, Monoid-Homomorphismus-Definition 'rausnehmen. Stattdessen: ausgehend von beliebigen Funktionen $h\colon \Sigma \to \mathbb {N}$, die man z.B. "Zeichenbewertung" nennen könnte, ohne große Umschweife eine "Wortbewertung" $h^{*}\colon \Sigma ^{*}\to \mathbb {N}$ definieren - per explizitem "$h^{*}(a_{1}\ldots a_{n}):=h(a_{1})+\ldots +h(a_{n})$". Fertig. Das steht zwar in Worten auch mehr oder weniger in der Einleitung, aber die Formel macht das superklar und unmissverständlich, ohne dass der Leser den einschlägigen Jargon kennen muss. Dann kann man vll. erwähnen, dass $h^{*}(\alpha \circ \beta )=h^{*}(\alpha )+h^{*}(\beta )$, aber das dürfte der geneigte Leser so schon sehen. Halbwegs sinnvoll wäre diese Erwähnung, wenn man umgekehrt sagt, dass Funktionen $\Sigma ^{*}\to \mathbb {N}$ mit dieser Eigenschaft auch wieder eindeutig zu Zeichenbewertungen gemacht werden können. An der Sinnhaftigkeit dessen habe ich allerdings auch Zweifel, denn die Texte in den Umgebungen von Links auf den Artikel machen davon keinen Gebrauch, wie mir scheint.

Zu Punkt 2: Dies war natürlich auch eins der Dinge, die mir einfielen, hat aber den Stempel "ja, darf 'Länge' heißen" nicht gekriegt. War mir nicht eindimensional genug. :) Wie auch immer, die Behauptung "Man kann zeigen, dass es Sprachen mit einer quasimonotonen Grammatik der Länge n gibt, so dass alle monotonen Grammatiken mindestens die Länge 2^n besitzen." muss ja irgendwo herkommen, und dort muss dann auch eine brauchbare Definition sein, die vll. auch die anderen Unstimmigkeiten ausräumt. Hier herumzuraten bringt nicht viel. --Daniel5Ko (Diskussion) 17:30, 8. Feb. 2013 (CET)

Zu Punkt 3: Sieht für mich gut aus. Mach's doch so, aber mit $h^{*}(a_{1}\dotso a_{n}):=h(a_{1})+\dotsb +h(a_{n})$ (s. Hilfe:TeX#Auslassungspunkte). -- UKoch (Diskussion) 19:15, 8. Feb. 2013 (CET)

Öhm, wieso ich? Mir liegt nichts an dem Artikel, und für mein Empfinden ist das nicht mal ein global sinnvoller Fachbegriff. Ich geb' hier nur meinen Sempf ab, weil Du mich drum gebeten hast. :) --Daniel5Ko (Diskussion) 00:34, 9. Feb. 2013 (CET)

OK, dann mach ich's demnächst. -- UKoch (Diskussion) 20:30, 11. Feb. 2013 (CET)

Es ist nur eine fancy Ausdrucksweise dafür, dass man jedem Zeichen eine natürliche Zahl zuordnet und jedem Wort dann die Summe all dieser Werte der Zeichen, aus denen es besteht. Die Aussage über kontextsensitive Sprachen kann nicht stimmen: Bzgl. der Nullfunktion als Bewertungsfunktion erfüllt nämlich jede Typ-0-Grammatik diese „Quasimonotonie“, nicht nur die, die kontextsensitive Sprachen erzeugen. --Chricho ¹ ² ³ 21:20, 7. Feb. 2013 (CET)

Jo, das mit der fancy Ausdrucksweise ist schon klar. Zur Aussage über kontextsensitive Sprachen: Die ist ja auf kontextsensitive Grammatiken eingeschränkt und spricht nicht allgemein von Typ-0-Grammatiken. Das kann natürlich auch ein Fehler sein. Was sagt die Literatur? -- UKoch (Diskussion) 16:04, 8. Feb. 2013 (CET)

Dann macht die Aussage doch auch keinen Sinn mehr, ich verstehe es so, dass es um bestimmte nicht kontextsensitive Grammatiken geht, die aber eine kontextsensitive Sprache erzeugen. --Chricho ¹ ² ³ 16:40, 8. Feb. 2013 (CET)

Stimmt. Aber welche? Wenn wir's nicht wissen und nichts in der Literatur finden, werden wir die Aussage streichen müssen. Ich frage mal Benutzer:Zahnradzacken. -- UKoch (Diskussion) 16:45, 8. Feb. 2013 (CET)

Danke fürs Informieren, aber was soll ich dazu schon sagen? Ich habe das Wort im Zusammenhang mit formalen Sprachen noch nicht gesehen. Die Aussage klingt spektakulär (und falsch) und ich weiß nicht, was eigentlich gemeint war. --Zahnradzacken (Diskussion) 22:53, 8. Feb. 2013 (CET)

Hm, schade -- ich hatte gehofft, Du und Daniel5Ko wisst alles, was ich nicht weiß. :-) Ich habe jetzt Benutzer:Bunt gefragt. -- UKoch (Diskussion) 20:30, 11. Feb. 2013 (CET)

Allgemein: Haben wir eine Chance, den Artikel so umzubauen, dass der Unverständlichkeits-Baustein weg kann? -- UKoch (Diskussion) 16:04, 8. Feb. 2013 (CET)

Ja, indem wir Literatur finden, die sagt, wozu der Begriff gut ist. Die fehlt hier leider… --Chricho ¹ ² ³ 00:40, 9. Feb. 2013 (CET)

... zumindest bisher. Ich habe jetzt Benutzer:Bunt gefragt; vielleicht antwortet er ja. -- UKoch (Diskussion) 20:30, 11. Feb. 2013 (CET)

Im Artikel Wachsend kontextsensitive Sprache desselben Autors steht mehr, insbesondere stehen da Quellen. In dem Kontext finde ich auch etwa dieses Paper, die Aussage, die hier im Artikel steht (bzw. stehen soll), finde ich aber auf die Schnelle nicht. --Chricho ¹ ² ³ 11:04, 27. Apr. 2013 (CEST)

Danke für den Link, aber ich find's da auch nicht. Ich habe auch ein bisschen gesucht, aber nichts gefunden. -- UKoch (Diskussion) 01:21, 4. Mai 2013 (CEST)

November 2013

Ich habe

• die Def. so vereinfacht, wie Daniel5Ko oben vorschlägt,
• die Einleitung verbessert (hoffentlich) und
• die falsche Aussage, von der wir nicht wissen, durch welche richtige Aussage sie zu ersetzen wäre, gelöscht.

Dabei habe ich die Bausteine entfernt. -- UKoch (Diskussion) 17:21, 29. Nov. 2013 (CET)