Bewertungsfunktion (Formale Sprachen)

Bewertungsfunktion (Formale Sprachen)

In der Theorie der Formalen Sprachen werden mit einer Bewertungsfunktion die Zeichen eines Alphabets bewertet. Die additive Fortsetzung auf alle Wörter des Alphabets wird dann zu einer Bewertung der Wörter über dem Alphabet.

Definition

Es sei Σ ein Alphabet. Eine Bewertungsfunktion ist ein Monoid-Homomorphismus vom freien Monoid über \Gamma\cup Q in die natürlichen Zahlen (mit 0):

h:((\Gamma\cup Q)^*,\circ)\rightarrow(\mathbb{N},+),
h(ε) = 0
für alle Wörter v,w\in(\Gamma\cup Q)^* gilt: h(v)+h(w)=h(v\circ w).

Hier bezeichnet ε das leere Wort und \circ die Konkatenation.

Beispiele

  1. Die Länge der Wörter liefert eine Bewertungsfunktion.
  2. Die konstante Nullfunktion liefert eine Bewertungsfunktion; d.h., wenn alle Zeichen den Wert 0 erhalten, dann ist die so additiv fortgesetzte Abbildung eine Bewertungsfunktion.
  3. Sei \Sigma_n:=\{a_1,a_2,\ldots,a_n\} ein n-elementiges Alphabet. Dann ist h_{exp}:\Sigma^*\rightarrow\mathbb{N} definiert durch: hexp(ai): = 2i
    Offenbar liefert die Fortsetzung dieser Abbildung wieder eine Bewertung.

Motivation

  1. Die kontextsensitiven Sprachen sind durch monotone Grammatiken charakterisiert. Das sind solche, die die Eigenschaft haben, dass die linke Seite nie länger als die rechte Seite ist.
  2. Diese Eigenschaft lässt sich verallgemeinern:
    Die kontextsensitiven Sprachen sind durch Grammatiken charakterisiert, die die Eigenschaft haben: es gibt eine kontextsensitive Grammatik mit der Eigenschaft: es existiert eine Bewertung aller Zeichen dieser Grammatik, so dass alle Regeln bezüglich dieser Bewertung die Eigenschaft haben: die linke Seite ist nie höher bewertet als die rechte. Solche Grammatiken heißen auch Quasimonoton.

Das interessante an quasimotonen Grammatiken ist, dass sie für manche Sprachen wesentlich kürzer sind als die äquivalente monotone Grammatik. Man kann zeigen, es gibt Sprachen mit einer quasimonotonen Grammatik der Länge n, so dass alle monotonen Grammatiken die Länge mindestens 2n besitzen. Offensichtlich können solche monotonen Grammatiken sehr unhandlich sein.

Weitere Anwendungen finden sich bei den Zweikellerautomaten.


Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • True Wert — Die Aussagenlogik (veraltet Urteilslogik) ist der Bereich der Logik, der sich mit Aussagen und deren Verknüpfung durch Junktoren befasst, ausgehend von strukturlosen Elementaraussagen (Atomen), denen semantisch ein Wahrheitswert zugeordnet wird.… …   Deutsch Wikipedia

  • Urteilslogik — Die Aussagenlogik (veraltet Urteilslogik) ist der Bereich der Logik, der sich mit Aussagen und deren Verknüpfung durch Junktoren befasst, ausgehend von strukturlosen Elementaraussagen (Atomen), denen semantisch ein Wahrheitswert zugeordnet wird.… …   Deutsch Wikipedia

  • Aussagenlogik — Die Aussagenlogik ist ein Teilgebiet der Logik, das sich mit Aussagen und deren Verknüpfung durch Junktoren befasst, ausgehend von strukturlosen Elementaraussagen (Atomen), denen ein Wahrheitswert zugeordnet wird. In der klassischen Aussagenlogik …   Deutsch Wikipedia

  • Logik erster Ordnung — Die Artikel Prädikatenlogik und Prädikat (Logik) überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese Überschneidungen. Bitte entferne diesen… …   Deutsch Wikipedia

  • PK1 — Die Artikel Prädikatenlogik und Prädikat (Logik) überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese Überschneidungen. Bitte entferne diesen… …   Deutsch Wikipedia

  • Prädikatenkalkül — Die Artikel Prädikatenlogik und Prädikat (Logik) überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese Überschneidungen. Bitte entferne diesen… …   Deutsch Wikipedia

  • Prädikatenlogik — oder Quantorenlogik ist eine Familie logischer Systeme, die es erlauben, einen weiten und in der Praxis vieler Wissenschaften und deren Anwendungen wichtigen Bereich von Argumenten zu formalisieren und auf ihre Gültigkeit zu überprüfen. Auf Grund …   Deutsch Wikipedia

  • Prädikatenlogik zweiter Stufe — Die Artikel Prädikatenlogik und Prädikat (Logik) überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese Überschneidungen. Bitte entferne diesen… …   Deutsch Wikipedia

  • Prädikatorenlogik — Die Artikel Prädikatenlogik und Prädikat (Logik) überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese Überschneidungen. Bitte entferne diesen… …   Deutsch Wikipedia

  • Quantorenlogik — Die Artikel Prädikatenlogik und Prädikat (Logik) überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese Überschneidungen. Bitte entferne diesen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”