Alphabet und Symbole 185

Definition

Als Alphabet bezeichnen wir eine endliche, nicht-leere Menge $\Sigma$. Elemente aus $w\in\Sigma$ heißen Zeichen oder Symbole.

• $\Sigma^{*}=$ Menge aller Wörter, die sich aus $\Sigma$ bilden lassen incl. leerem Wort $\varepsilon$
• $\Sigma^{+}=$ Menge aller Wörter, die sich aus $\Sigma$ bilden lassen ohne $\varepsilon$
• $\left\vert\Sigma\right\vert=$ Anzahl der verschiedenen Symbole in $\Sigma$ (Mächtigkeit der Menge $\Sigma$)

Konkatenation

Sei $\circ$ ein Symbol für die Konkatenation, dann ist die algebraische Struktur $\left(\Sigma^{*},\circ\right)$ eine Halbgruppe mit neutralem Element, ein so genanntes Monoid.

• Abgeschlossenheit
  $x\in\Sigma^{*}\wedge y\in\Sigma^{*}\Rightarrow x\circ y=xy\in\Sigma^{*}$
• Assoziativität
  $\left(x\circ y\right)\circ z=x\circ\left(y\circ z\right)=xyz$
• neutrales Element
  $\varepsilon\circ x=x\circ\varepsilon=x$

Wort

Ein Wort (mathm. ein Tupel) entsteht durch hintereinanderschreiben (Konkatenation) von Symbolen aus $\Sigma$. $\varepsilon$ steht für das leere Wort (eine art neutrales Element).

• $w^{n}=\underbrace{ww\ldots w}_{n-mal}\quad\left(n\in\mathbb{N}_{0}\right)$
• $w^{0}=\varepsilon$

Länge eines Wortes

Für ein Wort $w$ bezeichnet $\left\vert w\right\vert$ seine Länge, d.h. die Anzahl der in ihm enthaltenen Zeichen.

• $\left\vert\varepsilon\right\vert=0$
• $\left\vert uv\right\vert=\left\vert u\right\vert+\left\vert v\right\vert$
• $\left\vert w^{n}\right\vert=n\left\vert w\right\vert$

Diese Regeln haben eine gewisse Ähnlichkeit mit derer der Logarithmus Funktion.