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: h_exp(a_i): = 2ⁱ
   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 2ⁿ besitzen. Offensichtlich können solche monotonen Grammatiken sehr unhandlich sein.

Weitere Anwendungen finden sich bei den Zweikellerautomaten.