Es sei \( \Sigma=\left\{a_{1}, a_{2}, \ldots, a_{n}\right\} \) ein endliches Alphabet. Der Umnumerierungsoperator \( U_{k} \) sei dann wie folgt definiert: (i, \( k \in \mathbb{Z}, m, n \in \mathbb{N} \backslash\{0\}) \)
ist \( \alpha=\left\{\left(i, a_{i}\right),\left(i+1, a_{i+1}\right), \ldots,\left(m, a_{m}\right)\right\} \in \Sigma^{*} \), dann sei
\( U_{k}(\alpha):=\left\{\left(i+k, a_{i}\right),\left(i+k+1, a_{i+1}\right), \ldots,\left(m+k, a_{m}\right)\right\} \)
a) während a i.A. kein Wort im Sinne unserer Definition ist (wann ist es eines?), kann man mit \( U_{k}(\alpha) \) jedoch ein solches erzeugen (mit welchem \( \left.\mathrm{k} ?\right) \).
b) Wenn man die Hintereinanderausführung "*" zweier Umnumerierungen als Verknüpfung betrachtet, was ergibt dann \( \left(U_{k}{ }^{*} U_{1}\right)(\alpha) \) ?
c) Zeigen Sie, dass die Menge der Umnumerierungsoperatoren mit der Verknüpfung aus b) eine abelsche Gruppe bilden.
Definition:
Sei \( \Sigma \) ein Alphabet.
1) \( \Sigma^{*} \) ist die Menge aller Wörter über \( \Sigma \) (Achtung: \( \left.\varepsilon \in \Sigma^{*}\right) \).
2) \( \Sigma_{*}^{+}:=\Sigma^{*} \backslash\{\varepsilon\} \) ist die Menge aller nichtleeren Wörter über \( \Sigma \).
3) \( \Sigma_{\mathrm{n}}^{*}\left(\mathrm{bzw} \cdot \Sigma_{\mathrm{n}}^{+}\right) \)ist die Menge aller (nichtleeren) Wörter der Länge \( \mathbf{n} \in \mathbb{N} \) über \( \Sigma \).
4) \( \Sigma_{<n}^{*}\left(\right. \) bzw \( \left.. \Sigma_{<n}^{+}\right) \)ist die Menge (nichtleeren) aller Wörter der Länge kleiner \( n \in \mathbb{N} \) über \( \Sigma \).
Bemerkung:
1) \( \Sigma_{0}^{*}=\{\varepsilon\}, \Sigma_{1}^{*}=\Sigma \)
2) \( \Sigma_{<n}^{*}=\Sigma_{0}^{*} \cup \Sigma_{1}^{*} U \ldots \cup \Sigma_{n-1}^{*} \)
3) \( \Sigma^{*}=\bigcup_{\mathrm{k}=0}^{\infty} \Sigma_{\mathrm{k}}^{*} \)
Definition:
Sei \( \Sigma \) ein Alphabet und \( \alpha=a_{1} a_{2} \ldots a_{m}, \beta=b_{1} b_{2} \ldots b_{n} \in \Sigma^{*} \)
1) \( \alpha \) und \( \beta \) heissen gleich \( (\alpha=\beta) \Leftrightarrow m=n \) und \( a_{k}=b_{k} \) für alle \( 1 \leq k \leq n \)
2) \( \alpha \) heisst Teilwort von \( \beta(\alpha \sqsubseteq \beta) \Leftrightarrow \) es gibt ein
\( k \in\{1, \ldots, n\} \), so dass für alle \( i \in\{1, \ldots, m\} \) gilt : \( a_{i}=b_{i+k} \)
3) \( \alpha \) heisst echtes Teilwort von \( \beta \Leftrightarrow \alpha \subseteq \beta \) und \( \alpha \neq \beta \)
