Das Kefk Network Wiki befindet sich im Testbetrieb.

Standardnummerierung

Aus Kefk.

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 $\Sigma^* \$ ist wie folgt definiert:

Sei $\Sigma \$ ein Alphabet, $n:=card(\Sigma) \$ .
Sei $a:\{1,...n\} \rightarrow \Sigma$ eine Bijektion (eine Ordnungsfunktion) mit $a_i := a(i) \$ .

$\sigma:\Sigma^* \rightarrow \mathbb{N}$ sei definiert durch:

$\sigma(\varepsilon) := 0 \$ und
$\sigma(a_{i_k} a_{i_{k-1}}...a_{i_1} a_{i_0}) := i_kn^k+i_{k-1}n^{k-1}+...+i_1n+i_0$

für alle $k \in \mathbb{N}, i_0,\dots i_k \in \{1, \dots n\}$ .

Dann heißt $\nu_\Sigma:\mathbb{N} \rightarrow \Sigma^*$ , definiert durch $\nu_\Sigma:=\sigma^{-1} \$ , eine Standardnummerierung von $\Sigma^* \$ .

Beispiel

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

$\varepsilon$

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=1 \$ und $a(2)=a_2=2 \$ .

$\nu_\Sigma(i):= \$ das i-te Wort in der Liste, also $\nu_\Sigma(8)= \$ " $\mathrm{112} \$ ".

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Standardnummerierung, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.

Von „http://www.kefk.org/wiki/Standardnummerierung“

Kategorien: Theoretische Informatik | Wikipedia