Wort: Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung |
Keine Bearbeitungszusammenfassung |
||
| Zeile 1: | Zeile 1: | ||
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 <math>w</math> | ==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>: | |||
== | :<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]] | ||
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]] | ||