Assessment function (formal languages)

In the theory of formal languages , a branch of theoretical computer science , an evaluation function maps the characters of an alphabet to natural numbers . The additive continuation to all words above the alphabet then becomes an evaluation of the words above the alphabet.

definition

Let it be an alphabet and a character evaluation. (Here 0 is also a natural number.) The associated word evaluation or evaluation function is : ${\displaystyle \Sigma }$ ${\displaystyle h\colon \Sigma \to \mathbb {N} }$ ${\displaystyle h^{*}\colon \Sigma ^{*}\to \mathbb {N} }$

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

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

Examples

1. The length of the words provides an evaluation function.
2. The constant null function provides an evaluation function; d. That is, if all characters receive the value 0, then the mapping continued in this way is an evaluation function.
3. Be an -element alphabet. Then be defined by: . Obviously, the continuation of this figure again provides an assessment. ${\displaystyle \Sigma _{n}:=\{a_{1},a_{2},\dotsc ,a_{n}\}}$ ${\displaystyle n}$ ${\displaystyle h_{\text{exp}}\colon \Sigma ^{*}\rightarrow \mathbb {N} }$ ${\displaystyle h_{\text{exp}}(a_{i}):=2^{i}}$

motivation

The context-sensitive languages are characterized by monotonous grammars . These are those that have the property that the left side of a rule is never longer than the right side. This property can be generalized with the help of evaluation functions.

Further applications can be found with the two-cellar machines .