- Standardnummerierung
-
Eine Nummerierung einer Menge M ist eine surjektive (nicht zwingend bijektive) Funktion
, 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
eine Bijektion (eine Ordnungsfunktion) mit ai: = a(i).
sei definiert durch σ(ε): = 0 und
für alle
.
- Dann heißt
, definiert durch
, eine Standardnummerierung von
.
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.
, denn a(1) = a1 = 1 und a(2) = a2 = 2.
νΣ(i): = das i-te Wort in der Liste, also νΣ(8) = 112.
Wikimedia Foundation.