Wort: Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung |
Keine Bearbeitungszusammenfassung |
||
| Zeile 2: | Zeile 2: | ||
==Definition== | ==Definition== | ||
Es sei <math>\Sigma</math> ein [[Alphabet]] (eine endliche, nicht leere [[Menge]] von [[Zeichen]]). Ein '''Wort''' <math>w</math> über dem Alphabet <math>\Sigma</math> ist eine endliche Folge von <math>n</math> Zeichen <math>a_1 | Es sei <math>\Sigma</math> ein [[Alphabet]] (eine endliche, nicht leere [[Menge]] von [[Zeichen]]). Ein '''Wort''' <math>w</math> über dem Alphabet <math>\Sigma</math> ist eine endliche Folge von <math>n</math> Zeichen <math>a_1; a_2; \dots; a_n</math> mit <math>a_i \in \Sigma</math> und <math>n \in \mathbb{N}_0</math>: | ||
:<math>w = a_1 a_2 \dots a_n</math> | :<math>w = a_1 a_2 \dots a_n</math> | ||
| Zeile 19: | Zeile 19: | ||
===Verkettung (Konkatenation)=== | ===Verkettung (Konkatenation)=== | ||
Werden zwei Wörter <math>u \in \Sigma^*</math> und <math>v \in \Sigma^*</math> direkt hintereinander gehängt, entsteht ein neues Wort <math>uv \in \Sigma^*</math>. Diese Operation heißt '''Verkettung''' oder '''Konkatenation'''. | Werden zwei Wörter <math>u \in \Sigma^*</math> und <math>v \in \Sigma^*</math> direkt hintereinander gehängt, entsteht ein neues Wort <math>uv \in \Sigma^*</math>. Diese Operation heißt '''Verkettung''' oder '''Konkatenation'''. | ||
- '''Additivität der Wortlänge:''' Die Länge des verketteten Wortes ist die Summe der Einzellängen: <math>|uv| = |u| + |v|</math>. | |||
- '''Reihenfolge (Nicht-Kommutativität):''' Bei einem Wort kommt es exakt auf die Reihenfolge der Zeichen an. Im Allgemeinen sind <math>uv</math> und <math>vu</math> verschiedene Wörter (<math>uv \neq vu</math>). | |||
- '''Neutrales Element:''' Das Verketten mit dem leeren Wort <math>\varepsilon</math> verändert ein Wort nicht: <math>w\varepsilon = \varepsilon w = w</math>. | |||
- '''Wortpotenz:''' Wird dasselbe Wort oder Zeichen <math>k</math>-mal hintereinander gehängt, schreibt man verkürzt <math>w^k</math> (wobei <math>w^0 = \varepsilon</math> festgelegt ist). | |||
==Wörter und formale Sprachen== | ==Wörter und formale Sprachen== | ||
| Zeile 31: | Zeile 31: | ||
==Beispiele== | ==Beispiele== | ||
===Wörter, Wortlängen und Verkettungen bestimmen=== | ===Wörter, Wortlängen und Verkettungen bestimmen=== | ||
Gegeben sei das Alphabet <math>\Sigma = \{E | Gegeben sei das Alphabet <math>\Sigma = \{E; K\}</math>. Aus diesen beiden Zeichen lassen sich unter anderem folgende Wörter aus <math>\Sigma^*</math> bilden und untersuchen: | ||
- '''Wortlängen bestimmen:''' | |||
** Das Wort <math>w_1 = KEK</math> besteht aus drei Zeichen, hat also die Wortlänge <math>|KEK| = 3</math>. | ** Das Wort <math>w_1 = KEK</math> besteht aus drei Zeichen, hat also die Wortlänge <math>|KEK| = 3</math>. | ||
** Das Wort <math>w_2 = KKKK</math> (in Potenzschreibweise <math>K^4</math>) hat die Wortlänge <math>|KKKK| = 4</math>. | ** Das Wort <math>w_2 = KKKK</math> (in Potenzschreibweise <math>K^4</math>) hat die Wortlänge <math>|KKKK| = 4</math>. | ||
** Das leere Wort <math>\varepsilon</math> enthält kein Zeichen und besitzt die Wortlänge <math>|\varepsilon| = 0</math>. | ** Das leere Wort <math>\varepsilon</math> enthält kein Zeichen und besitzt die Wortlänge <math>|\varepsilon| = 0</math>. | ||
- '''Wörter verketten:''' Gegeben seien die Wörter <math>u = EK</math> (mit <math>|u| = 2</math>) und <math>v = K</math> (mit <math>|v| = 1</math>). | |||
** Das Anhängen von <math>v</math> an <math>u</math> ergibt <math>uv = EKK</math> mit der Länge <math>|uv| = |u| + |v| = 2 + 1 = 3</math>. | ** Das Anhängen von <math>v</math> an <math>u</math> ergibt <math>uv = EKK</math> mit der Länge <math>|uv| = |u| + |v| = 2 + 1 = 3</math>. | ||
** In umgekehrter Reihenfolge entsteht <math>vu = KEK</math>. Da die Zeichen an unterschiedlichen Positionen stehen, gilt <math>uv \neq vu</math>. | ** In umgekehrter Reihenfolge entsteht <math>vu = KEK</math>. Da die Zeichen an unterschiedlichen Positionen stehen, gilt <math>uv \neq vu</math>. | ||
| Zeile 43: | Zeile 43: | ||
===Akzeptierte und abgelehnte Wörter am Kaffeeautomaten unterscheiden=== | ===Akzeptierte und abgelehnte Wörter am Kaffeeautomaten unterscheiden=== | ||
[[Datei:DEA Kaffeeautomat vollständig.png|mini|Vollständiger DEA des Kaffeeautomaten]] | [[Datei:DEA Kaffeeautomat vollständig.png|mini|Vollständiger DEA des Kaffeeautomaten]] | ||
Der abgebildete Kaffeeautomat besitzt das Eingabealphabet <math>\Sigma = \{E | Der abgebildete Kaffeeautomat besitzt das Eingabealphabet <math>\Sigma = \{E; K\}</math>. Ein Kaffee <math>K</math> füllt das Satzfach um 1 Einheit, ein Espresso <math>E</math> um 2 Einheiten. Der Automat startet im Zustand <math>q_0</math> (0 Einheiten) und akzeptiert genau die Wörter, nach deren Eingabe er sich im doppelt umkreisten Endzustand <math>q_4</math> (Satzfach mit genau 4 Einheiten voll) befindet: | ||
- '''Akzeptierte Wörter (<math>w \in L</math>):''' Genau fünf Wörter über <math>\Sigma</math> führen vom Startzustand <math>q_0</math> in den Endzustand <math>q_4</math> und bilden die akzeptierte Sprache: | |||
:<math>L = \{KKKK | :<math>L = \{KKKK; EE; EKK; KEK; KKE\}</math> | ||
- '''Abgelehnte Wörter (<math>w \in \Sigma^*</math>, aber <math>w \notin L</math>):''' Alle übrigen Wörter aus <math>\Sigma^*</math> sind zwar formal gültige Wörter über dem Alphabet <math>\Sigma</math>, gehören aber nicht zur Sprache <math>L</math>: | |||
** <math>KK</math> (<math>|KK| = 2</math>): Nach zwei Kaffees endet der Automat im Zustand <math>q_2</math>. Da <math>q_2</math> kein Endzustand ist, gilt <math>KK \notin L</math>. | ** <math>KK</math> (<math>|KK| = 2</math>): Nach zwei Kaffees endet der Automat im Zustand <math>q_2</math>. Da <math>q_2</math> kein Endzustand ist, gilt <math>KK \notin L</math>. | ||
** <math>EEK</math> (<math>|EEK| = 3</math>): Nach <math>EE</math> ist zwar <math>q_4</math> erreicht, das anschließende <math>K</math> führt jedoch weiter in den Fehlerzustand <math>q_5</math> (Überlauf bei 5 Einheiten). Daher gilt <math>EEK \notin L</math>. | ** <math>EEK</math> (<math>|EEK| = 3</math>): Nach <math>EE</math> ist zwar <math>q_4</math> erreicht, das anschließende <math>K</math> führt jedoch weiter in den Fehlerzustand <math>q_5</math> (Überlauf bei 5 Einheiten). Daher gilt <math>EEK \notin L</math>. | ||
Version vom 10. November 2026, 09:22 Uhr
In der Informatik ist ein Wort jede endliche Zeichenfolge, die sich aus den Zeichen eines festgelegten Alphabets zusammensetzt – etwa ein Passwort, eine Binärzahl oder eine Folge von Tastendrücken. Ob die Zeichenfolge inhaltlich einen Sinn ergibt, spielt dabei keine Rolle.
Definition
Es sei [math]\displaystyle{ \Sigma }[/math] ein Alphabet (eine endliche, nicht leere Menge von Zeichen). Ein Wort [math]\displaystyle{ w }[/math] über dem Alphabet [math]\displaystyle{ \Sigma }[/math] ist eine endliche Folge von [math]\displaystyle{ n }[/math] Zeichen [math]\displaystyle{ a_1; a_2; \dots; a_n }[/math] mit [math]\displaystyle{ a_i \in \Sigma }[/math] und [math]\displaystyle{ n \in \mathbb{N}_0 }[/math]:
- [math]\displaystyle{ w = a_1 a_2 \dots a_n }[/math]
Besteht die Folge aus gar keinem Zeichen ([math]\displaystyle{ n = 0 }[/math]), heißt sie leeres Wort und wird mit dem griechischen Buchstaben [math]\displaystyle{ \varepsilon }[/math] (Epsilon) oder seltener mit [math]\displaystyle{ \lambda }[/math] (Lambda) bezeichnet.
Die Menge aller endlichen Wörter, die sich aus den Zeichen des Alphabets [math]\displaystyle{ \Sigma }[/math] bilden lassen (einschließlich des leeren Wortes [math]\displaystyle{ \varepsilon }[/math]), heißt Kleenesche Hülle [math]\displaystyle{ \Sigma^* }[/math]. Für [math]\displaystyle{ w \in \Sigma^* }[/math] liest man: „[math]\displaystyle{ w }[/math] ist ein Wort über [math]\displaystyle{ \Sigma }[/math]“. Die Menge aller Wörter ohne das leere Wort wird mit [math]\displaystyle{ \Sigma^+ = \Sigma^* \setminus \{\varepsilon\} }[/math] bezeichnet.
Eigenschaften und Operationen
Wortlänge
Die Wortlänge [math]\displaystyle{ |w| }[/math] gibt die Gesamtzahl der Zeichen an, aus denen das Wort [math]\displaystyle{ w }[/math] besteht. Kommt dasselbe Zeichen mehrfach im Wort vor, wird jedes Auftreten einzeln mitgezählt. Für ein Wort [math]\displaystyle{ w = a_1 a_2 \dots a_n }[/math] gilt [math]\displaystyle{ |w| = n }[/math].
Leeres Wort
Das leere Wort [math]\displaystyle{ \varepsilon }[/math] enthält kein einziges Zeichen, sodass für seine Wortlänge [math]\displaystyle{ |\varepsilon| = 0 }[/math] gilt. Es gehört zu jedem [math]\displaystyle{ \Sigma^* }[/math] ([math]\displaystyle{ \varepsilon \in \Sigma^* }[/math]), weil es kein Zeichen enthält, das außerhalb von [math]\displaystyle{ \Sigma }[/math] liegt. Das leere Wort selbst ist jedoch kein einzelnes Zeichen des Alphabets ([math]\displaystyle{ \varepsilon \notin \Sigma }[/math]).
Verkettung (Konkatenation)
Werden zwei Wörter [math]\displaystyle{ u \in \Sigma^* }[/math] und [math]\displaystyle{ v \in \Sigma^* }[/math] direkt hintereinander gehängt, entsteht ein neues Wort [math]\displaystyle{ uv \in \Sigma^* }[/math]. Diese Operation heißt Verkettung oder Konkatenation. - Additivität der Wortlänge: Die Länge des verketteten Wortes ist die Summe der Einzellängen: [math]\displaystyle{ |uv| = |u| + |v| }[/math]. - Reihenfolge (Nicht-Kommutativität): Bei einem Wort kommt es exakt auf die Reihenfolge der Zeichen an. Im Allgemeinen sind [math]\displaystyle{ uv }[/math] und [math]\displaystyle{ vu }[/math] verschiedene Wörter ([math]\displaystyle{ uv \neq vu }[/math]). - Neutrales Element: Das Verketten mit dem leeren Wort [math]\displaystyle{ \varepsilon }[/math] verändert ein Wort nicht: [math]\displaystyle{ w\varepsilon = \varepsilon w = w }[/math]. - Wortpotenz: Wird dasselbe Wort oder Zeichen [math]\displaystyle{ k }[/math]-mal hintereinander gehängt, schreibt man verkürzt [math]\displaystyle{ w^k }[/math] (wobei [math]\displaystyle{ w^0 = \varepsilon }[/math] festgelegt ist).
Wörter und formale Sprachen
Während [math]\displaystyle{ \Sigma^* }[/math] sämtliche Wörter enthält, die sich aus den Zeichen des Alphabets [math]\displaystyle{ \Sigma }[/math] bilden lassen, umfasst eine Formale Sprache [math]\displaystyle{ L \subseteq \Sigma^* }[/math] nur diejenigen Wörter, die zusätzliche formale Regeln erfüllen.
Prüft ein endlicher Automat [math]\displaystyle{ A }[/math] die Eingabewörter über [math]\displaystyle{ \Sigma }[/math], gehört ein Wort [math]\displaystyle{ w \in \Sigma^* }[/math] genau dann zur vom Automaten akzeptierten Sprache [math]\displaystyle{ L(A) }[/math], wenn sich der Automat nach dem vollständigen Lesen von [math]\displaystyle{ w }[/math] in einem Endzustand befindet. Ist bereits der Startzustand des Automaten ein Endzustand, wird auch das leere Wort [math]\displaystyle{ \varepsilon }[/math] akzeptiert ([math]\displaystyle{ \varepsilon \in L(A) }[/math]).
Beispiele
Wörter, Wortlängen und Verkettungen bestimmen
Gegeben sei das Alphabet [math]\displaystyle{ \Sigma = \{E; K\} }[/math]. Aus diesen beiden Zeichen lassen sich unter anderem folgende Wörter aus [math]\displaystyle{ \Sigma^* }[/math] bilden und untersuchen: - Wortlängen bestimmen:
- Das Wort [math]\displaystyle{ w_1 = KEK }[/math] besteht aus drei Zeichen, hat also die Wortlänge [math]\displaystyle{ |KEK| = 3 }[/math].
- Das Wort [math]\displaystyle{ w_2 = KKKK }[/math] (in Potenzschreibweise [math]\displaystyle{ K^4 }[/math]) hat die Wortlänge [math]\displaystyle{ |KKKK| = 4 }[/math].
- Das leere Wort [math]\displaystyle{ \varepsilon }[/math] enthält kein Zeichen und besitzt die Wortlänge [math]\displaystyle{ |\varepsilon| = 0 }[/math].
- Wörter verketten: Gegeben seien die Wörter [math]\displaystyle{ u = EK }[/math] (mit [math]\displaystyle{ |u| = 2 }[/math]) und [math]\displaystyle{ v = K }[/math] (mit [math]\displaystyle{ |v| = 1 }[/math]).
- Das Anhängen von [math]\displaystyle{ v }[/math] an [math]\displaystyle{ u }[/math] ergibt [math]\displaystyle{ uv = EKK }[/math] mit der Länge [math]\displaystyle{ |uv| = |u| + |v| = 2 + 1 = 3 }[/math].
- In umgekehrter Reihenfolge entsteht [math]\displaystyle{ vu = KEK }[/math]. Da die Zeichen an unterschiedlichen Positionen stehen, gilt [math]\displaystyle{ uv \neq vu }[/math].
- Die Verkettung mit dem leeren Wort ergibt [math]\displaystyle{ u\varepsilon = EK\varepsilon = EK = u }[/math].
Akzeptierte und abgelehnte Wörter am Kaffeeautomaten unterscheiden

Der abgebildete Kaffeeautomat besitzt das Eingabealphabet [math]\displaystyle{ \Sigma = \{E; K\} }[/math]. Ein Kaffee [math]\displaystyle{ K }[/math] füllt das Satzfach um 1 Einheit, ein Espresso [math]\displaystyle{ E }[/math] um 2 Einheiten. Der Automat startet im Zustand [math]\displaystyle{ q_0 }[/math] (0 Einheiten) und akzeptiert genau die Wörter, nach deren Eingabe er sich im doppelt umkreisten Endzustand [math]\displaystyle{ q_4 }[/math] (Satzfach mit genau 4 Einheiten voll) befindet:
- Akzeptierte Wörter ([math]\displaystyle{ w \in L }[/math]): Genau fünf Wörter über [math]\displaystyle{ \Sigma }[/math] führen vom Startzustand [math]\displaystyle{ q_0 }[/math] in den Endzustand [math]\displaystyle{ q_4 }[/math] und bilden die akzeptierte Sprache:
- [math]\displaystyle{ L = \{KKKK; EE; EKK; KEK; KKE\} }[/math]
- Abgelehnte Wörter ([math]\displaystyle{ w \in \Sigma^* }[/math], aber [math]\displaystyle{ w \notin L }[/math]): Alle übrigen Wörter aus [math]\displaystyle{ \Sigma^* }[/math] sind zwar formal gültige Wörter über dem Alphabet [math]\displaystyle{ \Sigma }[/math], gehören aber nicht zur Sprache [math]\displaystyle{ L }[/math]:
- [math]\displaystyle{ KK }[/math] ([math]\displaystyle{ |KK| = 2 }[/math]): Nach zwei Kaffees endet der Automat im Zustand [math]\displaystyle{ q_2 }[/math]. Da [math]\displaystyle{ q_2 }[/math] kein Endzustand ist, gilt [math]\displaystyle{ KK \notin L }[/math].
- [math]\displaystyle{ EEK }[/math] ([math]\displaystyle{ |EEK| = 3 }[/math]): Nach [math]\displaystyle{ EE }[/math] ist zwar [math]\displaystyle{ q_4 }[/math] erreicht, das anschließende [math]\displaystyle{ K }[/math] führt jedoch weiter in den Fehlerzustand [math]\displaystyle{ q_5 }[/math] (Überlauf bei 5 Einheiten). Daher gilt [math]\displaystyle{ EEK \notin L }[/math].
- [math]\displaystyle{ \varepsilon }[/math] ([math]\displaystyle{ |\varepsilon| = 0 }[/math]): Ohne Eingabe verbleibt der Automat im Startzustand [math]\displaystyle{ q_0 }[/math]. Da [math]\displaystyle{ q_0 }[/math] kein Endzustand ist, wird das leere Wort nicht akzeptiert ([math]\displaystyle{ \varepsilon \notin L }[/math]).