Bewertungsfunktion (Formale Sprachen)

In der Theorie der Formalen Sprachen, einem Teilgebiet der theoretischen Informatik, bildet eine Bewertungsfunktion die Zeichen eines Alphabets auf natürliche Zahlen ab. Die additive Fortsetzung auf alle Wörter über dem Alphabet wird dann zu einer Bewertung der Wörter über dem Alphabet.

Definition

Es sei ${\displaystyle \Sigma }$ ein Alphabet und ${\displaystyle h\colon \Sigma \to \mathbb {N} }$ eine Zeichenbewertung. (Hierbei sei auch 0 eine natürliche Zahl.) Die zugehörige Wortbewertung oder Bewertungsfunktion ist ${\displaystyle h^{*}\colon \Sigma ^{*}\to \mathbb {N} }$ mit:

${\displaystyle h^{*}(\varepsilon )=0}$

${\displaystyle h^{*}(a_{1}\dotso a_{n}):=h(a_{1})+\dotsb +h(a_{n})}$

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 ${\displaystyle \Sigma _{n}:=\{a_{1},a_{2},\dotsc ,a_{n}\}}$ ein ${\displaystyle n}$-elementiges Alphabet. Dann sei ${\displaystyle h_{\text{exp}}\colon \Sigma ^{*}\rightarrow \mathbb {N} }$ definiert durch: ${\displaystyle h_{\text{exp}}(a_{i}):=2^{i}}$. Offenbar liefert die Fortsetzung dieser Abbildung wieder eine Bewertung.

Motivation

Die kontextsensitiven Sprachen sind durch monotone Grammatiken charakterisiert. Das sind solche, die die Eigenschaft haben, dass die linke Seite einer Regel nie länger als die rechte Seite ist. Diese Eigenschaft lässt sich mit Hilfe von Bewertungsfunktionen verallgemeinern.

Weitere Anwendungen finden sich bei den Zweikellerautomaten.

Literatur

• G. Buntrock, K. Loryś: The variable membership problem: Succinctness versus complexity. Annual Symposium on Theoretical Aspects of Computer Science (STACS), 1994 – Springer Lecture Notes in Computer Science S. 593–606