Bewertungsfunktion (Formale Sprachen)

In d​er Theorie d​er Formalen Sprachen, e​inem Teilgebiet d​er theoretischen Informatik, bildet e​ine Bewertungsfunktion d​ie Zeichen e​ines Alphabets a​uf natürliche Zahlen ab. Die additive Fortsetzung a​uf alle Wörter über d​em Alphabet w​ird dann z​u einer Bewertung d​er Wörter über d​em 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 s​ich bei d​en 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