Standardnummerierung

Eine Nummerierung einer Menge M ist eine surjektive (nicht zwingend bijektive) Funktion $\nu : \subseteq \mathbb{N} \rightarrow M$, das heißt, jedem Element von M wird mindestens eine Nummer zugeordnet. Die Standardnummerierung einer Wortmenge Σ ^* ist wie folgt definiert:

• Sei Σ ein Alphabet, n: = card(Σ)
• Sei $a: \{1, \ldots , n\} \rightarrow \Sigma$ eine Bijektion (eine Ordnungsfunktion) mit a_i: = a(i).
• $\sigma: \Sigma^* \rightarrow \mathbb{N}$ sei definiert durch σ(ε): = 0 und $\sigma(a_{i_k} a_{i_{k-1}} \ldots a_{i_1} a_{i_0}) := i_kn^k + i_{k-1}n^{k-1} + \ldots + i_1n + i_0$ für alle $k \in \mathbb{N}, \ i_0, \ldots, i_k \in \{1, \ldots, n\}$.
• Dann heißt $\nu_\Sigma:\mathbb{N} \rightarrow \Sigma^*$, definiert durch $\nu_\Sigma := \sigma^{-1} \$, eine Standardnummerierung von $\Sigma^* \$.

Beispiel

Sei Σ = {1,2}. Die Menge Σ ^* kann systematisch aufgelistet werden:

ε,1,2,11,12,21,22,111,112,121,122,211,212,221,222,usw.

$\sigma(112) = 1 \cdot 2^2 + 1 \cdot 2^1 + 2 \cdot 2^0 = 8$, denn a(1) = a₁ = 1 und a(2) = a₂ = 2.

ν_Σ(i): = das i-te Wort in der Liste, also ν_Σ(8) = 112.