Wort (theoretische Informatik)

In der theoretischen Informatik ist ein Wort eine endliche Folge von Symbolen eines Alphabets. Im Gegensatz zur natürlichsprachlichen Bedeutung von Wörtern, die stets eine eigenständige Bedeutung haben, bezeichnet der Ausdruck Wort in der theoretischen Informatik lediglich eine Zeichenkette und nicht deren mögliche Bedeutung.

Wörter oder Worte^[1] sind die Elemente einer formalen Sprache. Sie sind deshalb wichtig für mathematische Modellierungen, für die Theorie der Programmiersprachen, für die Berechenbarkeitstheorie und andere Gebiete der theoretischen Informatik.

Definition

Es sei $\Sigma$ ein gegebenes Alphabet und $n$ eine natürliche Zahl aus $\mathbb {N} _{0}$ , der Menge der natürlichen Zahlen einschließlich der Null ( $\mathbb {N} _{0}=\{0,1,2,\ldots \}$ ). Ein Wort $w$ der Länge $n$ ist eine endliche Folge $(x_{1},x_{2},x_{3},\ldots ,x_{n})$ mit $x_{i}\in \Sigma$ für alle $i\in \{1,\ldots ,n\}$ .

Die Länge $n$ eines Wortes $w$ wird als $|w|$ notiert; die Zahl, wie oft das Zeichen $x$ im Wort $w$ vorkommt, mit $|w|_{x}$ .^[2]^[3] Ein besonderes Wort ist das leere Wort, das aus keinem Symbol besteht (die Länge 0 besitzt) und meist mit dem griechischen Buchstaben $\varepsilon$ (Epsilon) dargestellt wird (auch $\Lambda$ findet man gelegentlich^[4]). Die Menge aller Wörter, die man aus einem Alphabet $\Sigma$ bilden kann, ist die Kleenesche und positive Hülle über diesem Alphabet. Diese ist die disjunkte Vereinigung

\Sigma ^{*}:=\bigcup _{n\in \mathbb {N} \cup \{0\}}\Sigma ^{n}

.

Die nichtleeren Wörter sind dann entsprechend die ‚positive Hülle’

\Sigma ^{+}:=\Sigma ^{*}\setminus \{\varepsilon \}=\bigcup _{n\in \mathbb {N} }\Sigma ^{n}

.

Zur Angabe eines Wortes wird oft die vereinfachte Schreibweise $w=x_{1}x_{2}x_{3}\ldots x_{n}$ benutzt, was jedoch nur möglich ist, wenn das verwendete Alphabet eine eindeutige Zuordnung der benutzten Symbole zulässt. So kann diese Kurzschreibweise beim Alphabet $\Sigma =\{a,aa\}$ nicht angewendet werden, da hier zum Beispiel aus der Schreibweise $w=aaa$ nicht eindeutig hervorgeht, ob das Wort $(a,aa)$ , $(aa,a)$ oder $(a,a,a)$ gemeint ist.

Wörter der Länge $n$ können wie folgt aufgefasst werden:^[5]

als endliche Folgen (Sequenz) – da Tupel als Folgen mit endlicher Länge $n$ aufgefasst werden können
als Elemente des $n$ -fachen kartesischen Produktes – da Tupel auch so aufgefasst werden können

Beispiele

Es sei $\Sigma _{1}$ das Alphabet der lateinischen Buchstaben und $\Sigma _{2}=\lbrace \diamondsuit ,\heartsuit ,\spadesuit ,\clubsuit \rbrace$ . Dann sind die Wörter Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle w_{1}=haus} und $w_{2}=xyzzy$ Beispiele für Wörter über $\Sigma _{1}$ und Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle w_{3}=\heartsuit \clubsuit \clubsuit \heartsuit \spadesuit } ist ein Wort über $\Sigma _{2}$ . Man erkennt, dass $|w_{1}|=4$ und $|w_{2}|=|w_{3}|=5$ ist.

Operationen auf Wörtern

Konkatenation

Die Konkatenation oder Verkettung ist eine Verknüpfung zweier Wörter zu einem neuen Wort, das durch Aneinanderhängen der beiden Symbolfolgen entsteht. Die Konkatenation der beiden Wörter $x$ und $y$ über einem Alphabet $\Sigma$ wird mit $xy$ oder $x\circ y$ angegeben und ist definiert durch:

xy=x\circ y:=(x_{1},x_{2},x_{3},\ldots ,x_{n},y_{1},y_{2},y_{3},\ldots ,y_{k})

Dabei ist nach der Definition des Wortes $x=(x_{1},x_{2},x_{3},\ldots ,x_{n})$ und $y=(y_{1},y_{2},y_{3},\ldots ,y_{k})$ mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n,k \in \mathbb{N}_{0}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{i},y_{j} \in \Sigma} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i \in \{ 1, \ldots, n \}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j \in \{ 1, \ldots, k \}} . Nach der obigen Definition ist $x$ ein Präfix und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y} ein Suffix des durch die Konkatenation entstandenen Wortes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \circ y} . Die Länge eines konkatenierten Wortes entspricht dabei der Summe der Längen der einzelnen (Teil-)Wörter. So gilt für jedes Wort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u} und $v$ :

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |u \circ v| = |u| + |v|} ,

und für die absolute Häufigkeit eines Zeichens $x$ :

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |u \circ v|_x = |u|_x + |v|_x} .

Das neutrale Element der Konkatenation ist das leere Wort, da für jedes beliebige Wort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} gilt, dass:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w \circ \varepsilon = \varepsilon \circ w = w}

Da außerdem die Konkatenation assoziativ ist, bildet das Tripel Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\Sigma^*,\circ,\varepsilon)} aus der Menge aller Wörter über einem beliebigen Alphabet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma} , der Verknüpfung der Konkatenation und dem leeren Wort als neutralem Element ein Monoid. Die Assoziativität bedeutet, dass ohne weiteres Klammern weggelassen werden können:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (haus \circ \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit) \circ xyzzy = haus \circ( \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit \circ xyzzy) = haus \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit xyzzy}

Demgegenüber ist die Konkatenation nicht kommutativ, d. h. nicht für alle Wörter Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} gilt, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u \circ v = v \circ u} ist. So ist zum Beispiel:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle haus \circ \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit = haus \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit \not= \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit haus = \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit \circ haus}

Potenz

Die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -te Potenz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w^n} eines Wortes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} ist definiert als die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (n-1)} -fache Konkatenation dieses Wortes mit sich selbst. Die Definition der Potenz wird meist rekursiv angegeben:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w^{0} := \varepsilon}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w^{n+1} := w^{n} \circ w} (für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n \in \mathbb{N}_{0}} )

So sind zum Beispiel:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (xyzzy)^0 = \varepsilon}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\heartsuit \clubsuit \clubsuit \heartsuit \spadesuit)^1 = (\heartsuit \clubsuit \clubsuit \heartsuit \spadesuit)^0 \,\circ\, \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit = \varepsilon \,\circ\, \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit = \heartsuit \clubsuit \clubsuit \heartsuit \spadesuit}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (haus)^3=(haus)^2 \,\circ\, haus = ((haus)^1 \,\circ\, haus) \,\circ\, haus = ((\varepsilon \,\circ\, haus) \,\circ\, haus) \,\circ\, haus = haushaushaus}

Nach der Definition der Konkatenation ist die Länge der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} -ten Potenz eines beliebigen Wortes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} gleich dem Produkt aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} und der Länge von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} :

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |w^n| = n \cdot |w|} ,

und für die absolute Häufigkeit eines jeden Zeichens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} :

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |w^n|_x = n \cdot |w|_x}

Spiegelung

Die Spiegelung oder das Reverse Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w^R} eines Wortes $w$ ergibt sich, wenn man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} rückwärts schreibt.^[6] Wenn also $w=(x_{1},x_{2},x_{3},\ldots ,x_{n})$ ist, so ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w^R} die endliche Folge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (y_{1}, y_{2}, y_{3}, \ldots, y_{k})} mit $k=n$ und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y_{i} = x_{n+1-i}} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i \in \{ 1, \ldots, k \}} . Die Länge eines Wortes ist also gleich der Länge seiner Spiegelung:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |w^R| = |w|}

So gilt zum Beispiel für die folgenden Wörter:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon^R = \varepsilon}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (abb)^R = bba}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\heartsuit \clubsuit \spadesuit \heartsuit)^R = \heartsuit \spadesuit \clubsuit \heartsuit}

Das Reverse eines Wortes lässt sich außerdem mit Hilfe der strukturellen Induktion über dem Aufbau des betreffenden Wortes definieren. Dazu definiert man im Induktionsanfang das Reverse des leeren Wortes als das leere Wort. Im Induktionsschritt definiert man das Reverse eines aus einem Teilwort und einem Symbol zusammengesetzten Wortes als die Konkatenation des Symbols mit dem Reversen des Teilwortes:

Induktionsanfang: $w=\varepsilon \Rightarrow w^{R}=\varepsilon ^{R}:=\varepsilon$

Induktionsschritt: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (w=v \circ a) \land (v \in \Sigma^*, a \in \Sigma) \Rightarrow w^R = (v \circ a)^R := a \circ (v^R) }

So lässt sich schrittweise das Reverse eines Wortes herleiten:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon^R = \varepsilon }

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (abb)^R = b \circ (ab)^R = b \circ b \circ (a)^R = b \circ b \circ a \circ (\varepsilon)^R = b \circ b \circ a \circ \varepsilon = bba }

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\heartsuit \clubsuit \spadesuit \heartsuit)^R = \heartsuit \circ (\heartsuit \clubsuit \spadesuit)^R = \heartsuit \circ \spadesuit \circ (\heartsuit \clubsuit)^R = \heartsuit \circ \spadesuit \circ \clubsuit \circ (\heartsuit)^R = \heartsuit \spadesuit \clubsuit \heartsuit}

Ein Wort wie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle abaaba} , das identisch mit seiner Spiegelung ist, wird Palindrom genannt. Mathematisch werden diese spiegelsymmetrischen Worte als die Fixpunkte der Spiegelung ^R angesehen.

Präfix, Infix und Suffix

Infix

Ein Infix ist eine Hinzufügung innerhalb eines Wortes. Jede endliche Teilfolge von aufeinander folgenden Symbolen eines Wortes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} wird Infix oder Teilwort des Wortes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} genannt. Ein Infix eines gegebenen Wortes $w=(x_{1},x_{2},x_{3},\ldots ,x_{n})$ ist demnach jedes Wort ${\hat {w}}=(y_{1},y_{2},y_{3},\ldots ,y_{k})$ , für das es (mindestens) ein $i\in \mathbb {N} _{0}$ gibt, für das gilt, dass zum einen $k+i\leq n$ und zum anderen $x_{j+i}=y_{j}$ für jedes $j\in \{1,\ldots ,k\}$ ist. Demnach ist ein Wort $u$ genau dann Infix eines Wortes $w$ , wenn gilt, dass es mindestens ein Wort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} und ein Wort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} aus der Kleeneschen Hülle über dem Alphabet von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} gibt, so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p \circ u \circ s = w} ist:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u} ist Infix von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w :\; \Longleftrightarrow \exists p,s \in \Sigma^\ast:\; p \circ u \circ s = w}

So ist das Wort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat w = aba} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat w \in \lbrace a , b \rbrace^*} ein Infix der Wörter Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle babaab} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle abaababb} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle aba} , nicht aber der Wörter Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle abba} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle babbaabbab} beziehungsweise des leeren Wortes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon} . In vielen Computersprachen ist für Infix die englische Bezeichnung

substring

gebräuchlich.

Speziell ist das leere Wort ein Infix jedes beliebigen Wortes, und jedes Wort ist ein Infix von sich selbst. Ein Infix eines beliebigen Wortes, das nicht identisch mit diesem ist, wird echtes Infix genannt.

Präfix

Ein Präfix ist eine Hinzufügung am Anfang eines Wortes. Ein Präfix eines Wortes $w=(x_{1},x_{2},x_{3},\ldots ,x_{n})$ ist demnach jedes Infix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat w = (y_{1}, y_{2}, y_{3}, \ldots, y_{k})} , für das gilt, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k \leq n} und $x_{j}=y_{j}$ für jedes $j\in \{1,\ldots ,k\}$ ist. Demnach ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u} genau dann Präfix des Wortes $w$ , wenn es mindestens ein $s$ aus der Kleeneschen Hülle über dem Alphabet, aus dem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} erzeugt wurde, gibt, so dass $u\circ s=w$ ist:

u

ist Präfix von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w :\; \Longleftrightarrow \exists s \in \Sigma^\ast:\; u \circ s = w}

Auch für Präfixe gilt, dass jedes Wort ein Präfix von sich selbst und das leere Wort ein Präfix jedes beliebigen Wortes ist. Ein Präfix eines Wortes, das nicht identisch mit ihm ist, wird echtes Präfix genannt.

Beispiel

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w = abaabb} , so lauten die echten Präfixe für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} :

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon}
$a$
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ab}
$aba$
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle abaa}
$abaab$ .

Suffix

Ein Suffix, auch Postfix genannt, ist eine Hinzufügung am Ende eines Wortes. Ein Suffix eines Wortes $w=(x_{1},x_{2},x_{3},\ldots ,x_{n})$ ist nach der Definition des Infixes jedes Teilwort ${\hat {w}}=(y_{1},y_{2},y_{3},\ldots ,y_{k})$ , für das gilt, dass es ein $i\in \mathbb {N} _{0}$ gibt, für das zum einen $k+i=n$ und zum anderen $x_{j+i}=y_{j}$ für jedes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j \in \{ 1, \ldots, k \}} ist. Demnach ist ein Wort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u} genau dann Suffix eines Wortes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w \in \Sigma^\ast} , wenn es mindestens ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p \in \Sigma^\ast} gibt, so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p \circ u = w} ist:

u

ist Suffix von

w:\;\Longleftrightarrow \exists p\in \Sigma ^{\ast }:\;p\circ u=w

Wie für Präfixe und Infixe gilt auch für Suffixe, dass das leere Wort ein Suffix jedes beliebigen Wortes und ein beliebiges Wort stets auch ein Suffix von sich selbst ist. Ein Suffix eines Wortes, das nicht identisch mit ihm ist, wird echtes Suffix genannt.

Beispiel

Sei $w=abaabb$ , so lauten die echten Suffixe für $w$ :

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle baabb}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle aabb}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle abb}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle bb}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon} .

Literatur

John E. Hopcroft, Jeffry D. Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 3. korrigierte Auflage. Addison-Wesley, Bonn u. a. 1994, ISBN 3-89319-744-3 (Internationale Computer-Bibliothek).
Katrin Erk, Lutz Priese: Theoretische Informatik. Eine umfassende Einführung. 2. erweiterte Auflage. Springer-Verlag, Berlin u. a. 2002, ISBN 3-540-42624-8, S. 27–28 (Springer-Lehrbuch).
Gottfried Vossen, Kurt-Ulrich Witt: Grundkurs theoretische Informatik. Eine anwendungsbezogene Einführung - für Studierende in allen Informatik-Studiengängen. 4. verbesserte und erweiterte Auflage. Vieweg, Wiesbaden 2006, ISBN 3-8348-0153-4, S. 15 (online).

Anmerkungen und Einzelnachweise

↑ Gebräuchlich sind beide Pluralformen, vgl. z. B. dtv-Atlas zur Mathematik, Bd. I, ISBN 3-423-03007-0, S. 245 versus Bauer, Goos: Informatik. Bd. I, ISBN 3-540-06332-3, S. 28.
↑ Klaus Reinhardt: Prioritätszählerautomaten und die Synchronisation von Halbspursprachen, Fakultät Informatik der Universität Stuttgart; Doktorarbeit 1994 (PDF; 509 KB)
↑ Dabei ist $|w|=\sum \limits _{x\in \Sigma }|w|_{x}$ .
↑ Yuri L. Ershov, Eugenii A. Palyutin: Mathematical Logic. Translated from the Russian by Vladimir Shokurov. Revised from the 1979 Russian edition. Mir Publishers, Moskau 1984, S. 16 (mirtitles.org).
↑ Definition von Tupel und seine Synonyme: Encyclopedia of Mathematics: Tuple
↑ Die Spiegelung eines Wortes der Länge n ist eine spezielle selbstinverse Permutation
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma_n = \begin{pmatrix} 1 & 2 & \cdots & n \\ n & n-1 & \cdots & 1 \end{pmatrix}} .
Die Spiegelung beliebig langer Wörter ist dann die Vereinigung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {}^R = \bigcup\{\sigma_n|n \in \N\}}

Weblinks

Grundbegriffe der formalen Sprache – Abschnitt „Wort“

[1] Gebräuchlich sind beide Pluralformen, vgl. z. B. dtv-Atlas zur Mathematik, Bd. I, ISBN 3-423-03007-0, S. 245 versus Bauer, Goos: Informatik. Bd. I, ISBN 3-540-06332-3, S. 28.

[KR1994-2] Klaus Reinhardt: Prioritätszählerautomaten und die Synchronisation von Halbspursprachen, Fakultät Informatik der Universität Stuttgart; Doktorarbeit 1994 (PDF; 509 KB)

[3] Dabei ist $|w|=\sum \limits _{x\in \Sigma }|w|_{x}$ .

[4] Yuri L. Ershov, Eugenii A. Palyutin: Mathematical Logic. Translated from the Russian by Vladimir Shokurov. Revised from the 1979 Russian edition. Mir Publishers, Moskau 1984, S. 16 (mirtitles.org).

[5] Definition von Tupel und seine Synonyme: Encyclopedia of Mathematics: Tuple

[6] Die Spiegelung eines Wortes der Länge n ist eine spezielle selbstinverse Permutation
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sigma_n = \begin{pmatrix} 1 & 2 & \cdots & n \\ n & n-1 & \cdots & 1 \end{pmatrix}} .
Die Spiegelung beliebig langer Wörter ist dann die Vereinigung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {}^R = \bigcup\{\sigma_n|n \in \N\}}

[1]

[2]

[3]

[4]

[5]

[6]

Anonym

Suche

Wort (theoretische Informatik)

Namensräume

Mehr

Seitenaktionen

Inhaltsverzeichnis

Definition

Beispiele