Zum Inhalt springen

Wort: Unterschied zwischen den Versionen

Aus FLBK-Wiki
Keine Bearbeitungszusammenfassung
Keine Bearbeitungszusammenfassung
Zeile 1: Zeile 1:
== Einführung ==
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.
Ein Wort über einem [[Alphabet]] ist eine endliche Folge von Buchstaben aus der Menge Σ des Eingabealphabets. Die Menge der Wörter, die von einem [[Automat|Automaten]] akzeptiert werden, nennt man die vom Automaten akzeptierte Sprache. Auch das leere Wort (leere Folge von Buchstaben) kann von einem Automaten akzeptiert werden. Es wird in der Regel mit den griechischen Buchstaben ε (Epsilon) oder λ (Lambda) beschrieben.


Ein Wort <math>w</math> gehört zur Sprache L des Automaten, wenn <math>w \in \Sigma^*</math> gilt und der Automat nach dem Lesen von <math>w</math> in einem Endzustand ist.
==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, a_2, \dots, a_n</math> mit <math>a_i \in \Sigma</math> und <math>n \in \mathbb{N}_0</math>:


== Beispiel ==
:<math>w = a_1 a_2 \dots a_n</math>
 
Besteht die Folge aus gar keinem Zeichen (<math>n = 0</math>), heißt sie '''leeres Wort''' und wird mit dem griechischen Buchstaben <math>\varepsilon</math> (Epsilon) oder seltener mit <math>\lambda</math> (Lambda) bezeichnet.
 
Die Menge aller endlichen Wörter, die sich aus den Zeichen des Alphabets <math>\Sigma</math> bilden lassen (einschließlich des leeren Wortes <math>\varepsilon</math>), heißt '''Kleenesche Hülle''' <math>\Sigma^*</math>. Für <math>w \in \Sigma^*</math> liest man: „<math>w</math> ist ein Wort über <math>\Sigma</math>“. Die Menge aller Wörter ohne das leere Wort wird mit <math>\Sigma^+ = \Sigma^* \setminus \{\varepsilon\}</math> bezeichnet.
 
==Eigenschaften und Operationen==
===Wortlänge===
Die '''Wortlänge''' <math>|w|</math> gibt die Gesamtzahl der Zeichen an, aus denen das Wort <math>w</math> besteht. Kommt dasselbe Zeichen mehrfach im Wort vor, wird jedes Auftreten einzeln mitgezählt. Für ein Wort <math>w = a_1 a_2 \dots a_n</math> gilt <math>|w| = n</math>.
 
===Leeres Wort===
Das leere Wort <math>\varepsilon</math> enthält kein einziges Zeichen, sodass für seine Wortlänge <math>|\varepsilon| = 0</math> gilt. Es gehört zu jedem <math>\Sigma^*</math> (<math>\varepsilon \in \Sigma^*</math>), weil es kein Zeichen enthält, das außerhalb von <math>\Sigma</math> liegt. Das leere Wort selbst ist jedoch kein einzelnes Zeichen des Alphabets (<math>\varepsilon \notin \Sigma</math>).
 
===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'''.
* '''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ährend <math>\Sigma^*</math> sämtliche Wörter enthält, die sich aus den Zeichen des Alphabets <math>\Sigma</math> bilden lassen, umfasst eine [[Formale Sprache]] <math>L \subseteq \Sigma^*</math> nur diejenigen Wörter, die zusätzliche formale Regeln erfüllen.
 
Prüft ein [[Endlicher Automat|endlicher Automat]] <math>A</math> die Eingabewörter über <math>\Sigma</math>, gehört ein Wort <math>w \in \Sigma^*</math> genau dann zur vom Automaten akzeptierten Sprache <math>L(A)</math>, wenn sich der Automat nach dem vollständigen Lesen von <math>w</math> in einem Endzustand befindet. Ist bereits der Startzustand des Automaten ein Endzustand, wird auch das leere Wort <math>\varepsilon</math> akzeptiert (<math>\varepsilon \in L(A)</math>).
 
==Beispiele==
===Wörter, Wortlängen und Verkettungen bestimmen===
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_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>.
* '''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>.
** In umgekehrter Reihenfolge entsteht <math>vu = KEK</math>. Da die Zeichen an unterschiedlichen Positionen stehen, gilt <math>uv \neq vu</math>.
** Die Verkettung mit dem leeren Wort ergibt <math>u\varepsilon = EK\varepsilon = EK = u</math>.
 
===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]]
Die vom Kaffeeautomaten akzeptierte Sprache ist L={KKKK, EE, EKK, KEK, KKE}. Alle anderen Wörter, die über das Eingabealphabet Σ={E,K} gebildet werden können, gehören nicht zu dieser Sprache.
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, 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>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>\varepsilon</math> (<math>|\varepsilon| = 0</math>): Ohne Eingabe verbleibt der Automat im Startzustand <math>q_0</math>. Da <math>q_0</math> kein Endzustand ist, wird das leere Wort nicht akzeptiert (<math>\varepsilon \notin L</math>).


[[Kategorie:Formale Sprachen]]
[[Kategorie:Formale Sprachen]]
[[Kategorie:AHR I Informatik LK]]
[[Kategorie:AHR I Informatik LK]]

Version vom 10. November 2026, 08:10 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

Vollständiger DEA des Kaffeeautomaten

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]).