Standardnummerierung

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 ai: = 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) = a1 = 1 und a(2) = a2 = 2.

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


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Abzählbar — In der Mengenlehre wird eine Menge A als abzählbar unendlich bezeichnet, wenn sie die gleiche Mächtigkeit hat wie die Menge der natürlichen Zahlen . Dies bedeutet, dass es eine Bijektion zwischen A und der Menge der natürlichen Zahlen gibt, die… …   Deutsch Wikipedia

  • Abzählbar unendlich — In der Mengenlehre wird eine Menge A als abzählbar unendlich bezeichnet, wenn sie die gleiche Mächtigkeit hat wie die Menge der natürlichen Zahlen . Dies bedeutet, dass es eine Bijektion zwischen A und der Menge der natürlichen Zahlen gibt, die… …   Deutsch Wikipedia

  • Abzählbare Menge — In der Mengenlehre wird eine Menge A als abzählbar unendlich bezeichnet, wenn sie die gleiche Mächtigkeit hat wie die Menge der natürlichen Zahlen . Dies bedeutet, dass es eine Bijektion zwischen A und der Menge der natürlichen Zahlen gibt, die… …   Deutsch Wikipedia

  • Überabzählbar unendlich — In der Mengenlehre wird eine Menge A als abzählbar unendlich bezeichnet, wenn sie die gleiche Mächtigkeit hat wie die Menge der natürlichen Zahlen . Dies bedeutet, dass es eine Bijektion zwischen A und der Menge der natürlichen Zahlen gibt, die… …   Deutsch Wikipedia

  • Abzählbarkeit — In der Mengenlehre wird eine Menge A als abzählbar unendlich bezeichnet, wenn sie die gleiche Mächtigkeit hat wie die Menge der natürlichen Zahlen . Dies bedeutet, dass es eine Bijektion zwischen A und der Menge der natürlichen Zahlen gibt, die… …   Deutsch Wikipedia

  • Anthracen — Strukturformel Allgemeines Name Anthracen Andere Namen P …   Deutsch Wikipedia

  • Berechenbar — In der Berechenbarkeitstheorie nennt man eine Funktion berechenbar, wenn es einen Algorithmus gibt, der die Funktion berechnet. Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe… …   Deutsch Wikipedia

  • Berechenbare Funktion — In der Berechenbarkeitstheorie nennt man eine Funktion berechenbar, wenn es einen Algorithmus gibt, der die Funktion berechnet. Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe… …   Deutsch Wikipedia

  • Miniterm — Als Vollkonjunktion (auch: Minterm, Miniterm oder Elementarkonjunktion) bezeichnet man in der Aussagenlogik einen speziellen Konjunktionsterm, d. h. eine Anzahl von Buchstaben (Literalen), die alle durch ein logisches und ( ) verknüpft sind.… …   Deutsch Wikipedia

  • Minterm — Als Vollkonjunktion (auch: Minterm, Miniterm oder Elementarkonjunktion) bezeichnet man in der Aussagenlogik einen speziellen Konjunktionsterm, d. h. eine Anzahl von Buchstaben (Literalen), die alle durch ein logisches und ( ) verknüpft sind.… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”