Turingmaschine: Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung |
Keine Bearbeitungszusammenfassung Markierung: Zurückgesetzt |
||
| 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. | |||
==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; 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>\mathbb{N}_0</math> ist die Menge der natürlichen Zahlen einschließlich der Null. 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) bezeichnet. Manche Bücher schreiben dafür <math>\lambda</math> (Lambda). In diesem Wiki steht <math>\lambda</math> für die Ausgabefunktion des [[Mealy-Automat|Mealy-Automaten]]. | |||
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> (gelesen „Sigma Stern“). 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^+</math> (gelesen „Sigma Plus“) bezeichnet. Als [[Menge#Differenzmenge|Differenzmenge]] geschrieben gilt <math>\Sigma^+ = \Sigma^* \setminus \{\varepsilon\}</math>. | |||
Stern und Plus werden auch auf eine ausgeschriebene Menge von Zeichen angewendet. Die Menge steht dann in Mengenklammern vor dem Stern oder dem Plus, siehe das Beispiel [[#Kleenesche Hülle aufschreiben|Kleenesche Hülle aufschreiben]]. | |||
Anders als bei einer Menge kommt es bei einem Wort auf die Reihenfolge der Zeichen an, und dasselbe Zeichen darf mehrfach vorkommen. | |||
== | ==Eigenschaften und Operationen== | ||
Die | ===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), siehe [[#Wortpotenz|Wortpotenz]]. | |||
===Wortpotenz=== | |||
Die '''Wortpotenz''' <math>w^k</math> ist die <math>k</math>-fache Verkettung eines Wortes <math>w</math> mit sich selbst: | |||
:<math>w^k = \underbrace{w\,w \dots w}_{k\text{-mal}} \quad \text{mit } k \in \mathbb{N}_0</math> | |||
* Für <math>k = 0</math> entsteht das leere Wort: <math>w^0 = \varepsilon</math>. Für <math>k = 1</math> bleibt das Wort unverändert: <math>w^1 = w</math>. | |||
* Die Länge vervielfacht sich: <math>|w^k| = k \cdot |w|</math>. | |||
* Der Exponent bezieht sich nur auf das Zeichen direkt davor. Soll ein ganzes Wort wiederholt werden, steht es in Klammern. Die Klammern gehören dabei nicht zum Wort. | |||
* Steht im Exponenten eine Variable wie <math>n</math>, beschreibt die Potenz viele Wörter auf einmal: für jeden zulässigen Wert von <math>n</math> eines. So lassen sich auch unendliche [[Formale Sprache|Sprachen]] kurz angeben. | |||
===Teilwort=== | |||
Ein Wort <math>u</math> heißt '''Teilwort''' von <math>w</math>, wenn <math>u</math> als zusammenhängendes Stück in <math>w</math> vorkommt. Dann lässt sich <math>w</math> als Verkettung <math>w = xuy</math> mit zwei Wörtern <math>x \in \Sigma^*</math> und <math>y \in \Sigma^*</math> schreiben. | |||
* Steht <math>u</math> am Anfang von <math>w</math> (also <math>x = \varepsilon</math>), heißt <math>u</math> '''Präfix''' von <math>w</math>. | |||
* Steht <math>u</math> am Ende von <math>w</math> (also <math>y = \varepsilon</math>), heißt <math>u</math> '''Suffix''' von <math>w</math>. | |||
* Das leere Wort <math>\varepsilon</math> und das Wort <math>w</math> selbst sind Teilwörter von <math>w</math>. | |||
===Spiegelwort=== | |||
Das '''Spiegelwort''' <math>w^R</math> enthält die Zeichen von <math>w</math> in umgekehrter Reihenfolge (<math>R</math> für englisch ''reverse'', umgekehrt). Für <math>w = a_1 a_2 \dots a_n</math> gilt: | |||
:<math>w^R = a_n \dots a_2 a_1</math> | |||
* Die Wortlänge bleibt gleich: <math>|w^R| = |w|</math>. | |||
* Das leere Wort und jedes Wort aus einem einzigen Zeichen stimmen mit ihrem Spiegelwort überein. | |||
* Beim Spiegeln einer Verkettung kehrt sich auch die Reihenfolge der Teile um: <math>(uv)^R = v^R u^R</math>. | |||
* Ein Wort, das mit seinem Spiegelwort übereinstimmt (<math>w = w^R</math>), heißt '''Palindrom'''. | |||
==Anzahl der Wörter== | |||
Über einem Alphabet mit <math>m</math> Zeichen gibt es genau <math>m^n</math> Wörter der Länge <math>n</math>: Für jede der <math>n</math> Stellen stehen <math>m</math> Zeichen zur Wahl, und die Möglichkeiten werden multipliziert. | |||
Sind an den einzelnen Stellen unterschiedlich viele Zeichen erlaubt, werden die Anzahlen der erlaubten Zeichen aller Stellen miteinander multipliziert: Bei <math>m_1</math> Möglichkeiten für die erste Stelle, <math>m_2</math> für die zweite und so weiter bis <math>m_n</math> für die <math>n</math>-te Stelle gibt es <math>m_1 \cdot m_2 \cdot \dots \cdot m_n</math> Wörter. | |||
Die Menge aller Wörter der Länge <math>n</math> wird mit <math>\Sigma^n</math> bezeichnet. Damit gilt: | |||
* <math>\Sigma^0 = \{\varepsilon\}</math>: Es gibt genau ein Wort der Länge 0, das leere Wort. | |||
* <math>\Sigma^1</math> enthält die <math>m</math> Wörter, die aus einem einzigen Zeichen bestehen. | |||
* <math>\Sigma^* = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup \dots</math> enthält die Wörter aller Längen. Das Zeichen <math>\cup</math> steht für die [[Menge#Vereinigungsmenge|Vereinigung]] von Mengen. | |||
* <math>\Sigma^+ = \Sigma^1 \cup \Sigma^2 \cup \dots</math> enthält die Wörter aller Längen ab 1. | |||
Obwohl das Alphabet endlich ist und jedes einzelne Wort endlich lang ist, enthält <math>\Sigma^*</math> unendlich viele Wörter: Zu jedem Wort entsteht durch Anhängen eines Zeichens ein längeres Wort. | |||
==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. Sie ist eine [[Menge#Teilmenge|Teilmenge]] von <math>\Sigma^*</math>. | |||
Prüft ein [[Deterministischer endlicher Automat|deterministischer 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>). Bei einem [[Nichtdeterministischer endlicher Automat|nichtdeterministischen endlichen Automaten]] genügt es, wenn mindestens ein Pfad nach dem vollständigen Lesen in einem Endzustand endet. | |||
==Beispiele== | ==Beispiele== | ||
=== | ===Wörter, Wortlängen und Verkettungen bestimmen=== | ||
Gegeben sei das Alphabet <math>\Sigma = \{K; E\}</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>. | |||
===Wortpotenzen ausschreiben=== | |||
Über dem Alphabet <math>\Sigma = \{K; E\}</math> werden Potenzen ausgeschrieben und Wörter in Potenzschreibweise zusammengefasst: | |||
{| class="wikitable | {| class="wikitable" | ||
! | ! Potenzschreibweise !! ausgeschrieben !! Wortlänge | ||
|- | |- | ||
| <math> | | <math>K^3</math> || <math>KKK</math> || <math>3 \cdot 1 = 3</math> | ||
|- | |- | ||
| <math> | | <math>(KE)^2</math> || <math>KEKE</math> || <math>2 \cdot 2 = 4</math> | ||
|- | |- | ||
| <math> | | <math>KE^2</math> || <math>KEE</math> || <math>1 + 2 = 3</math> | ||
|- | |||
| <math>K^2E^3</math> || <math>KKEEE</math> || <math>2 + 3 = 5</math> | |||
|- | |||
| <math>(KE)^0</math> || <math>\varepsilon</math> || <math>0 \cdot 2 = 0</math> | |||
|} | |} | ||
Der Vergleich der Zeilen <math>(KE)^2</math> und <math>KE^2</math> zeigt die Wirkung der Klammern: In <math>(KE)^2</math> wird das ganze Wort <math>KE</math> wiederholt, in <math>KE^2</math> nur das Zeichen <math>E</math>. Umgekehrt lässt sich das Wort <math>KKKKEE</math> kürzer als <math>K^4E^2</math> schreiben. | |||
Mit einer Variablen im Exponenten steht <math>K^n</math> mit <math>n \ge 0</math> für die Wörter <math>\varepsilon</math>, <math>K</math>, <math>KK</math>, <math>KKK</math> und so weiter. <math>K^nE</math> mit <math>n \ge 1</math> beschreibt alle Wörter aus mindestens einem <math>K</math> und einem abschließenden <math>E</math>, also <math>KE</math>, <math>KKE</math>, <math>KKKE</math> und so weiter. | |||
=== | ===Kleenesche Hülle aufschreiben=== | ||
Gegeben ist das Alphabet <math>\Sigma = \{K; E\}</math>. Seine Wörter werden nach der Länge geordnet aufgeschrieben: | |||
{| class="wikitable | {| class="wikitable" | ||
! | ! Menge !! ausgeschrieben !! Anzahl der Wörter | ||
|- | |- | ||
| <math> | | <math>\Sigma^0</math> || <math>\{\varepsilon\}</math> || <math>2^0 = 1</math> | ||
|- | |- | ||
| <math> | | <math>\Sigma^1</math> || <math>\{K; E\}</math> || <math>2^1 = 2</math> | ||
|- | |- | ||
| <math> | | <math>\Sigma^2</math> || <math>\{KK; KE; EK; EE\}</math> || <math>2^2 = 4</math> | ||
|- | |- | ||
| <math> | | <math>\Sigma^3</math> || <math>\{KKK; KKE; KEK; KEE; EKK; EKE; EEK; EEE\}</math> || <math>2^3 = 8</math> | ||
|} | |} | ||
* '''Kleenesche Hülle:''' <math>\Sigma^*</math> enthält die Wörter aller Zeilen und alle längeren Wörter: <math>\Sigma^* = \{\varepsilon; K; E; KK; KE; EK; EE; KKK; \dots\}</math>. Die Aufzählung endet nie, das zeigen die drei Punkte an. | |||
* '''Ohne das leere Wort:''' <math>\Sigma^+ = \{K; E; KK; KE; EK; EE; KKK; \dots\}</math> enthält dieselben Wörter außer <math>\varepsilon</math>. | |||
* '''Stern über einer kleineren Menge:''' <math>\{K\}^* = \{\varepsilon; K; KK; KKK; \dots\}</math> enthält nur die Wörter, in denen kein anderes Zeichen als <math>K</math> vorkommt. <math>\{K\}^+</math> enthält dieselben Wörter außer <math>\varepsilon</math>. | |||
* '''Zugehörigkeit prüfen:''' Es gilt <math>KEK \in \Sigma^*</math> und <math>KEK \in \Sigma^+</math>, aber <math>KEK \notin \{K\}^*</math>, weil das Wort ein <math>E</math> enthält. Für das leere Wort gilt <math>\varepsilon \in \Sigma^*</math> und <math>\varepsilon \in \{K\}^*</math>, aber <math>\varepsilon \notin \Sigma^+</math>. | |||
* '''Teil eines größeren Alphabets:''' Über dem Alphabet <math>\{a; b; c\}</math> enthält <math>\{a; b\}^+</math> alle Wörter aus mindestens einem Zeichen, in denen nur <math>a</math> und <math>b</math> vorkommen. Dazu gehören <math>a</math>, <math>ab</math> und <math>bba</math>, nicht aber <math>\varepsilon</math> und <math>ac</math>. | |||
===Wörter aufzählen und zählen=== | |||
Gegeben ist das Alphabet <math>\Sigma = \{a; b; c\}</math> mit <math>m = 3</math> Zeichen. Gesucht sind alle Wörter bis zur Länge 2 und die Anzahl der Wörter der Länge 4. | |||
* '''Länge 0:''' Es gibt nur das leere Wort <math>\varepsilon</math>, also <math>3^0 = 1</math> Wort. | |||
* '''Länge 1:''' <math>a</math>, <math>b</math> und <math>c</math>, also <math>3^1 = 3</math> Wörter. | |||
* '''Länge 2:''' Jedes der 3 Zeichen an der ersten Stelle lässt sich mit jedem der 3 Zeichen an der zweiten Stelle kombinieren. Das ergibt <math>3^2 = 9</math> Wörter: <math>aa</math>, <math>ab</math>, <math>ac</math>, <math>ba</math>, <math>bb</math>, <math>bc</math>, <math>ca</math>, <math>cb</math> und <math>cc</math>. | |||
* '''Bis zur Länge 2:''' Zusammen sind das <math>1 + 3 + 9 = 13</math> Wörter. | |||
* '''Länge 4:''' Für vier Stellen gibt es <math>3^4 = 3 \cdot 3 \cdot 3 \cdot 3 = 81</math> Wörter. Aufzählen lohnt sich hier nicht mehr, die Formel <math>m^n</math> liefert die Anzahl direkt. | |||
=== | ===Wörter mit unterschiedlichen Stellen zählen=== | ||
Ein Kaffeeautomat bietet zwei Getränke an, Kaffee <math>K</math> und Espresso <math>E</math>, jeweils in drei Bechergrößen <math>1</math>, <math>2</math> und <math>3</math>. Eine Bestellung besteht aus genau zwei Zeichen: zuerst das Getränk, dann die Größe. Das Alphabet ist <math>\Sigma = \{K; E; 1; 2; 3\}</math>. | |||
* '''Möglichkeiten je Stelle:''' Für die erste Stelle gibt es 2 Zeichen, für die zweite Stelle 3 Zeichen. | |||
* '''Anzahl:''' Jedes Getränk lässt sich mit jeder Größe kombinieren. Es gibt <math>2 \cdot 3 = 6</math> Bestellungen. | |||
* '''Aufzählung:''' <math>K1</math>, <math>K2</math>, <math>K3</math>, <math>E1</math>, <math>E2</math> und <math>E3</math>. | |||
* '''Vergleich:''' Über <math>\Sigma</math> gibt es <math>5^2 = 25</math> Wörter der Länge 2. Nur 6 davon sind Bestellungen. Die Wörter <math>1K</math> und <math>KE</math> sind zum Beispiel keine. | |||
===Teilwörter erkennen=== | |||
Gegeben ist das Wort <math>w = KEKK</math> über <math>\Sigma = \{K; E\}</math>. | |||
* <math>EK</math> ist ein Teilwort von <math>w</math>: Es gilt <math>w = xuy</math> mit <math>x = K</math>, <math>u = EK</math> und <math>y = K</math>. | |||
* <math>KE</math> ist ein Präfix von <math>w</math>, denn <math>w</math> beginnt mit <math>KE</math>. | |||
* <math>KK</math> ist ein Suffix von <math>w</math>, denn <math>w</math> endet mit <math>KK</math>. | |||
* <math>EE</math> ist kein Teilwort von <math>w</math>, denn in <math>w</math> stehen nirgends zwei <math>E</math> direkt hintereinander. | |||
* <math>KKK</math> ist kein Teilwort von <math>w</math>: Das Wort enthält zwar drei <math>K</math>, aber nicht zusammenhängend. | |||
* Alle Präfixe von <math>w</math> sind <math>\varepsilon</math>, <math>K</math>, <math>KE</math>, <math>KEK</math> und <math>KEKK</math>. Alle Suffixe von <math>w</math> sind <math>\varepsilon</math>, <math>K</math>, <math>KK</math>, <math>EKK</math> und <math>KEKK</math>. | |||
* | ===Spiegelwörter bilden=== | ||
Gegeben sind Wörter über <math>\Sigma = \{K; E\}</math>. | |||
* <math>(KKE)^R = EKK</math>: Das Wort wird von hinten nach vorn gelesen. Die Klammern gehören nicht zum Wort, sie zeigen nur, worauf sich das <math>R</math> bezieht. | |||
* <math>(KEK)^R = KEK</math>: Das Wort stimmt mit seinem Spiegelwort überein, es ist ein Palindrom. | |||
* Für <math>u = KK</math> und <math>v = E</math> ist <math>uv = KKE</math>. Das Spiegelwort entsteht auch aus den gespiegelten Teilen in umgekehrter Reihenfolge: Mit <math>v^R = E</math> und <math>u^R = KK</math> ergibt sich <math>v^R u^R = EKK</math>. | |||
* Hängt man an ein Wort <math>u</math> sein Spiegelwort an, entsteht ein spiegelbildlich aufgebautes Wort <math>u\,u^R</math>. Für <math>u = KE</math> ist <math>u^R = EK</math> und damit <math>u\,u^R = KEEK</math>: Die zweite Hälfte wiederholt die erste in umgekehrter Reihenfolge. | |||
===Akzeptierte und abgelehnte Wörter am Kaffeeautomaten unterscheiden=== | |||
[[Datei:DEA Kaffeeautomat vollständig.png|mini|Vollständiger DEA des Kaffeeautomaten]] | |||
Der abgebildete Kaffeeautomat besitzt das Eingabealphabet <math>\Sigma = \{K; E\}</math>. Er sammelt den Kaffeesatz in einem Behälter, dem Satzfach. 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 [[Deterministischer endlicher Automat#Vollständiger DEA und Fehlerzustand|Fehlerzustand]] <math>q_F</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>). | |||
Die Zustandsfolgen dieser Wörter stehen Schritt für Schritt im Beispiel [[Deterministischer endlicher Automat#Wortzugehörigkeit mit einem DEA prüfen|Wortzugehörigkeit mit einem DEA prüfen]]. Einen Automaten, der das leere Wort akzeptiert, zeigt das Beispiel [[Deterministischer endlicher Automat#DEA für Reste entwerfen|DEA für Reste entwerfen]]. | |||
[[Kategorie: | [[Kategorie:Formale Sprachen]] | ||
[[Kategorie:AHR I Informatik LK]] | [[Kategorie:AHR I Informatik LK]] | ||
Version vom 11. November 2026, 22:08 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]
[math]\displaystyle{ \mathbb{N}_0 }[/math] ist die Menge der natürlichen Zahlen einschließlich der Null. 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) bezeichnet. Manche Bücher schreiben dafür [math]\displaystyle{ \lambda }[/math] (Lambda). In diesem Wiki steht [math]\displaystyle{ \lambda }[/math] für die Ausgabefunktion des Mealy-Automaten.
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] (gelesen „Sigma Stern“). 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^+ }[/math] (gelesen „Sigma Plus“) bezeichnet. Als Differenzmenge geschrieben gilt [math]\displaystyle{ \Sigma^+ = \Sigma^* \setminus \{\varepsilon\} }[/math].
Stern und Plus werden auch auf eine ausgeschriebene Menge von Zeichen angewendet. Die Menge steht dann in Mengenklammern vor dem Stern oder dem Plus, siehe das Beispiel Kleenesche Hülle aufschreiben.
Anders als bei einer Menge kommt es bei einem Wort auf die Reihenfolge der Zeichen an, und dasselbe Zeichen darf mehrfach vorkommen.
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), siehe Wortpotenz.
Wortpotenz
Die Wortpotenz [math]\displaystyle{ w^k }[/math] ist die [math]\displaystyle{ k }[/math]-fache Verkettung eines Wortes [math]\displaystyle{ w }[/math] mit sich selbst:
- [math]\displaystyle{ w^k = \underbrace{w\,w \dots w}_{k\text{-mal}} \quad \text{mit } k \in \mathbb{N}_0 }[/math]
- Für [math]\displaystyle{ k = 0 }[/math] entsteht das leere Wort: [math]\displaystyle{ w^0 = \varepsilon }[/math]. Für [math]\displaystyle{ k = 1 }[/math] bleibt das Wort unverändert: [math]\displaystyle{ w^1 = w }[/math].
- Die Länge vervielfacht sich: [math]\displaystyle{ |w^k| = k \cdot |w| }[/math].
- Der Exponent bezieht sich nur auf das Zeichen direkt davor. Soll ein ganzes Wort wiederholt werden, steht es in Klammern. Die Klammern gehören dabei nicht zum Wort.
- Steht im Exponenten eine Variable wie [math]\displaystyle{ n }[/math], beschreibt die Potenz viele Wörter auf einmal: für jeden zulässigen Wert von [math]\displaystyle{ n }[/math] eines. So lassen sich auch unendliche Sprachen kurz angeben.
Teilwort
Ein Wort [math]\displaystyle{ u }[/math] heißt Teilwort von [math]\displaystyle{ w }[/math], wenn [math]\displaystyle{ u }[/math] als zusammenhängendes Stück in [math]\displaystyle{ w }[/math] vorkommt. Dann lässt sich [math]\displaystyle{ w }[/math] als Verkettung [math]\displaystyle{ w = xuy }[/math] mit zwei Wörtern [math]\displaystyle{ x \in \Sigma^* }[/math] und [math]\displaystyle{ y \in \Sigma^* }[/math] schreiben.
- Steht [math]\displaystyle{ u }[/math] am Anfang von [math]\displaystyle{ w }[/math] (also [math]\displaystyle{ x = \varepsilon }[/math]), heißt [math]\displaystyle{ u }[/math] Präfix von [math]\displaystyle{ w }[/math].
- Steht [math]\displaystyle{ u }[/math] am Ende von [math]\displaystyle{ w }[/math] (also [math]\displaystyle{ y = \varepsilon }[/math]), heißt [math]\displaystyle{ u }[/math] Suffix von [math]\displaystyle{ w }[/math].
- Das leere Wort [math]\displaystyle{ \varepsilon }[/math] und das Wort [math]\displaystyle{ w }[/math] selbst sind Teilwörter von [math]\displaystyle{ w }[/math].
Spiegelwort
Das Spiegelwort [math]\displaystyle{ w^R }[/math] enthält die Zeichen von [math]\displaystyle{ w }[/math] in umgekehrter Reihenfolge ([math]\displaystyle{ R }[/math] für englisch reverse, umgekehrt). Für [math]\displaystyle{ w = a_1 a_2 \dots a_n }[/math] gilt:
- [math]\displaystyle{ w^R = a_n \dots a_2 a_1 }[/math]
- Die Wortlänge bleibt gleich: [math]\displaystyle{ |w^R| = |w| }[/math].
- Das leere Wort und jedes Wort aus einem einzigen Zeichen stimmen mit ihrem Spiegelwort überein.
- Beim Spiegeln einer Verkettung kehrt sich auch die Reihenfolge der Teile um: [math]\displaystyle{ (uv)^R = v^R u^R }[/math].
- Ein Wort, das mit seinem Spiegelwort übereinstimmt ([math]\displaystyle{ w = w^R }[/math]), heißt Palindrom.
Anzahl der Wörter
Über einem Alphabet mit [math]\displaystyle{ m }[/math] Zeichen gibt es genau [math]\displaystyle{ m^n }[/math] Wörter der Länge [math]\displaystyle{ n }[/math]: Für jede der [math]\displaystyle{ n }[/math] Stellen stehen [math]\displaystyle{ m }[/math] Zeichen zur Wahl, und die Möglichkeiten werden multipliziert.
Sind an den einzelnen Stellen unterschiedlich viele Zeichen erlaubt, werden die Anzahlen der erlaubten Zeichen aller Stellen miteinander multipliziert: Bei [math]\displaystyle{ m_1 }[/math] Möglichkeiten für die erste Stelle, [math]\displaystyle{ m_2 }[/math] für die zweite und so weiter bis [math]\displaystyle{ m_n }[/math] für die [math]\displaystyle{ n }[/math]-te Stelle gibt es [math]\displaystyle{ m_1 \cdot m_2 \cdot \dots \cdot m_n }[/math] Wörter.
Die Menge aller Wörter der Länge [math]\displaystyle{ n }[/math] wird mit [math]\displaystyle{ \Sigma^n }[/math] bezeichnet. Damit gilt:
- [math]\displaystyle{ \Sigma^0 = \{\varepsilon\} }[/math]: Es gibt genau ein Wort der Länge 0, das leere Wort.
- [math]\displaystyle{ \Sigma^1 }[/math] enthält die [math]\displaystyle{ m }[/math] Wörter, die aus einem einzigen Zeichen bestehen.
- [math]\displaystyle{ \Sigma^* = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup \dots }[/math] enthält die Wörter aller Längen. Das Zeichen [math]\displaystyle{ \cup }[/math] steht für die Vereinigung von Mengen.
- [math]\displaystyle{ \Sigma^+ = \Sigma^1 \cup \Sigma^2 \cup \dots }[/math] enthält die Wörter aller Längen ab 1.
Obwohl das Alphabet endlich ist und jedes einzelne Wort endlich lang ist, enthält [math]\displaystyle{ \Sigma^* }[/math] unendlich viele Wörter: Zu jedem Wort entsteht durch Anhängen eines Zeichens ein längeres Wort.
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. Sie ist eine Teilmenge von [math]\displaystyle{ \Sigma^* }[/math].
Prüft ein deterministischer 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]). Bei einem nichtdeterministischen endlichen Automaten genügt es, wenn mindestens ein Pfad nach dem vollständigen Lesen in einem Endzustand endet.
Beispiele
Wörter, Wortlängen und Verkettungen bestimmen
Gegeben sei das Alphabet [math]\displaystyle{ \Sigma = \{K; E\} }[/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].
Wortpotenzen ausschreiben
Über dem Alphabet [math]\displaystyle{ \Sigma = \{K; E\} }[/math] werden Potenzen ausgeschrieben und Wörter in Potenzschreibweise zusammengefasst:
| Potenzschreibweise | ausgeschrieben | Wortlänge |
|---|---|---|
| [math]\displaystyle{ K^3 }[/math] | [math]\displaystyle{ KKK }[/math] | [math]\displaystyle{ 3 \cdot 1 = 3 }[/math] |
| [math]\displaystyle{ (KE)^2 }[/math] | [math]\displaystyle{ KEKE }[/math] | [math]\displaystyle{ 2 \cdot 2 = 4 }[/math] |
| [math]\displaystyle{ KE^2 }[/math] | [math]\displaystyle{ KEE }[/math] | [math]\displaystyle{ 1 + 2 = 3 }[/math] |
| [math]\displaystyle{ K^2E^3 }[/math] | [math]\displaystyle{ KKEEE }[/math] | [math]\displaystyle{ 2 + 3 = 5 }[/math] |
| [math]\displaystyle{ (KE)^0 }[/math] | [math]\displaystyle{ \varepsilon }[/math] | [math]\displaystyle{ 0 \cdot 2 = 0 }[/math] |
Der Vergleich der Zeilen [math]\displaystyle{ (KE)^2 }[/math] und [math]\displaystyle{ KE^2 }[/math] zeigt die Wirkung der Klammern: In [math]\displaystyle{ (KE)^2 }[/math] wird das ganze Wort [math]\displaystyle{ KE }[/math] wiederholt, in [math]\displaystyle{ KE^2 }[/math] nur das Zeichen [math]\displaystyle{ E }[/math]. Umgekehrt lässt sich das Wort [math]\displaystyle{ KKKKEE }[/math] kürzer als [math]\displaystyle{ K^4E^2 }[/math] schreiben.
Mit einer Variablen im Exponenten steht [math]\displaystyle{ K^n }[/math] mit [math]\displaystyle{ n \ge 0 }[/math] für die Wörter [math]\displaystyle{ \varepsilon }[/math], [math]\displaystyle{ K }[/math], [math]\displaystyle{ KK }[/math], [math]\displaystyle{ KKK }[/math] und so weiter. [math]\displaystyle{ K^nE }[/math] mit [math]\displaystyle{ n \ge 1 }[/math] beschreibt alle Wörter aus mindestens einem [math]\displaystyle{ K }[/math] und einem abschließenden [math]\displaystyle{ E }[/math], also [math]\displaystyle{ KE }[/math], [math]\displaystyle{ KKE }[/math], [math]\displaystyle{ KKKE }[/math] und so weiter.
Kleenesche Hülle aufschreiben
Gegeben ist das Alphabet [math]\displaystyle{ \Sigma = \{K; E\} }[/math]. Seine Wörter werden nach der Länge geordnet aufgeschrieben:
| Menge | ausgeschrieben | Anzahl der Wörter |
|---|---|---|
| [math]\displaystyle{ \Sigma^0 }[/math] | [math]\displaystyle{ \{\varepsilon\} }[/math] | [math]\displaystyle{ 2^0 = 1 }[/math] |
| [math]\displaystyle{ \Sigma^1 }[/math] | [math]\displaystyle{ \{K; E\} }[/math] | [math]\displaystyle{ 2^1 = 2 }[/math] |
| [math]\displaystyle{ \Sigma^2 }[/math] | [math]\displaystyle{ \{KK; KE; EK; EE\} }[/math] | [math]\displaystyle{ 2^2 = 4 }[/math] |
| [math]\displaystyle{ \Sigma^3 }[/math] | [math]\displaystyle{ \{KKK; KKE; KEK; KEE; EKK; EKE; EEK; EEE\} }[/math] | [math]\displaystyle{ 2^3 = 8 }[/math] |
- Kleenesche Hülle: [math]\displaystyle{ \Sigma^* }[/math] enthält die Wörter aller Zeilen und alle längeren Wörter: [math]\displaystyle{ \Sigma^* = \{\varepsilon; K; E; KK; KE; EK; EE; KKK; \dots\} }[/math]. Die Aufzählung endet nie, das zeigen die drei Punkte an.
- Ohne das leere Wort: [math]\displaystyle{ \Sigma^+ = \{K; E; KK; KE; EK; EE; KKK; \dots\} }[/math] enthält dieselben Wörter außer [math]\displaystyle{ \varepsilon }[/math].
- Stern über einer kleineren Menge: [math]\displaystyle{ \{K\}^* = \{\varepsilon; K; KK; KKK; \dots\} }[/math] enthält nur die Wörter, in denen kein anderes Zeichen als [math]\displaystyle{ K }[/math] vorkommt. [math]\displaystyle{ \{K\}^+ }[/math] enthält dieselben Wörter außer [math]\displaystyle{ \varepsilon }[/math].
- Zugehörigkeit prüfen: Es gilt [math]\displaystyle{ KEK \in \Sigma^* }[/math] und [math]\displaystyle{ KEK \in \Sigma^+ }[/math], aber [math]\displaystyle{ KEK \notin \{K\}^* }[/math], weil das Wort ein [math]\displaystyle{ E }[/math] enthält. Für das leere Wort gilt [math]\displaystyle{ \varepsilon \in \Sigma^* }[/math] und [math]\displaystyle{ \varepsilon \in \{K\}^* }[/math], aber [math]\displaystyle{ \varepsilon \notin \Sigma^+ }[/math].
- Teil eines größeren Alphabets: Über dem Alphabet [math]\displaystyle{ \{a; b; c\} }[/math] enthält [math]\displaystyle{ \{a; b\}^+ }[/math] alle Wörter aus mindestens einem Zeichen, in denen nur [math]\displaystyle{ a }[/math] und [math]\displaystyle{ b }[/math] vorkommen. Dazu gehören [math]\displaystyle{ a }[/math], [math]\displaystyle{ ab }[/math] und [math]\displaystyle{ bba }[/math], nicht aber [math]\displaystyle{ \varepsilon }[/math] und [math]\displaystyle{ ac }[/math].
Wörter aufzählen und zählen
Gegeben ist das Alphabet [math]\displaystyle{ \Sigma = \{a; b; c\} }[/math] mit [math]\displaystyle{ m = 3 }[/math] Zeichen. Gesucht sind alle Wörter bis zur Länge 2 und die Anzahl der Wörter der Länge 4.
- Länge 0: Es gibt nur das leere Wort [math]\displaystyle{ \varepsilon }[/math], also [math]\displaystyle{ 3^0 = 1 }[/math] Wort.
- Länge 1: [math]\displaystyle{ a }[/math], [math]\displaystyle{ b }[/math] und [math]\displaystyle{ c }[/math], also [math]\displaystyle{ 3^1 = 3 }[/math] Wörter.
- Länge 2: Jedes der 3 Zeichen an der ersten Stelle lässt sich mit jedem der 3 Zeichen an der zweiten Stelle kombinieren. Das ergibt [math]\displaystyle{ 3^2 = 9 }[/math] Wörter: [math]\displaystyle{ aa }[/math], [math]\displaystyle{ ab }[/math], [math]\displaystyle{ ac }[/math], [math]\displaystyle{ ba }[/math], [math]\displaystyle{ bb }[/math], [math]\displaystyle{ bc }[/math], [math]\displaystyle{ ca }[/math], [math]\displaystyle{ cb }[/math] und [math]\displaystyle{ cc }[/math].
- Bis zur Länge 2: Zusammen sind das [math]\displaystyle{ 1 + 3 + 9 = 13 }[/math] Wörter.
- Länge 4: Für vier Stellen gibt es [math]\displaystyle{ 3^4 = 3 \cdot 3 \cdot 3 \cdot 3 = 81 }[/math] Wörter. Aufzählen lohnt sich hier nicht mehr, die Formel [math]\displaystyle{ m^n }[/math] liefert die Anzahl direkt.
Wörter mit unterschiedlichen Stellen zählen
Ein Kaffeeautomat bietet zwei Getränke an, Kaffee [math]\displaystyle{ K }[/math] und Espresso [math]\displaystyle{ E }[/math], jeweils in drei Bechergrößen [math]\displaystyle{ 1 }[/math], [math]\displaystyle{ 2 }[/math] und [math]\displaystyle{ 3 }[/math]. Eine Bestellung besteht aus genau zwei Zeichen: zuerst das Getränk, dann die Größe. Das Alphabet ist [math]\displaystyle{ \Sigma = \{K; E; 1; 2; 3\} }[/math].
- Möglichkeiten je Stelle: Für die erste Stelle gibt es 2 Zeichen, für die zweite Stelle 3 Zeichen.
- Anzahl: Jedes Getränk lässt sich mit jeder Größe kombinieren. Es gibt [math]\displaystyle{ 2 \cdot 3 = 6 }[/math] Bestellungen.
- Aufzählung: [math]\displaystyle{ K1 }[/math], [math]\displaystyle{ K2 }[/math], [math]\displaystyle{ K3 }[/math], [math]\displaystyle{ E1 }[/math], [math]\displaystyle{ E2 }[/math] und [math]\displaystyle{ E3 }[/math].
- Vergleich: Über [math]\displaystyle{ \Sigma }[/math] gibt es [math]\displaystyle{ 5^2 = 25 }[/math] Wörter der Länge 2. Nur 6 davon sind Bestellungen. Die Wörter [math]\displaystyle{ 1K }[/math] und [math]\displaystyle{ KE }[/math] sind zum Beispiel keine.
Teilwörter erkennen
Gegeben ist das Wort [math]\displaystyle{ w = KEKK }[/math] über [math]\displaystyle{ \Sigma = \{K; E\} }[/math].
- [math]\displaystyle{ EK }[/math] ist ein Teilwort von [math]\displaystyle{ w }[/math]: Es gilt [math]\displaystyle{ w = xuy }[/math] mit [math]\displaystyle{ x = K }[/math], [math]\displaystyle{ u = EK }[/math] und [math]\displaystyle{ y = K }[/math].
- [math]\displaystyle{ KE }[/math] ist ein Präfix von [math]\displaystyle{ w }[/math], denn [math]\displaystyle{ w }[/math] beginnt mit [math]\displaystyle{ KE }[/math].
- [math]\displaystyle{ KK }[/math] ist ein Suffix von [math]\displaystyle{ w }[/math], denn [math]\displaystyle{ w }[/math] endet mit [math]\displaystyle{ KK }[/math].
- [math]\displaystyle{ EE }[/math] ist kein Teilwort von [math]\displaystyle{ w }[/math], denn in [math]\displaystyle{ w }[/math] stehen nirgends zwei [math]\displaystyle{ E }[/math] direkt hintereinander.
- [math]\displaystyle{ KKK }[/math] ist kein Teilwort von [math]\displaystyle{ w }[/math]: Das Wort enthält zwar drei [math]\displaystyle{ K }[/math], aber nicht zusammenhängend.
- Alle Präfixe von [math]\displaystyle{ w }[/math] sind [math]\displaystyle{ \varepsilon }[/math], [math]\displaystyle{ K }[/math], [math]\displaystyle{ KE }[/math], [math]\displaystyle{ KEK }[/math] und [math]\displaystyle{ KEKK }[/math]. Alle Suffixe von [math]\displaystyle{ w }[/math] sind [math]\displaystyle{ \varepsilon }[/math], [math]\displaystyle{ K }[/math], [math]\displaystyle{ KK }[/math], [math]\displaystyle{ EKK }[/math] und [math]\displaystyle{ KEKK }[/math].
Spiegelwörter bilden
Gegeben sind Wörter über [math]\displaystyle{ \Sigma = \{K; E\} }[/math].
- [math]\displaystyle{ (KKE)^R = EKK }[/math]: Das Wort wird von hinten nach vorn gelesen. Die Klammern gehören nicht zum Wort, sie zeigen nur, worauf sich das [math]\displaystyle{ R }[/math] bezieht.
- [math]\displaystyle{ (KEK)^R = KEK }[/math]: Das Wort stimmt mit seinem Spiegelwort überein, es ist ein Palindrom.
- Für [math]\displaystyle{ u = KK }[/math] und [math]\displaystyle{ v = E }[/math] ist [math]\displaystyle{ uv = KKE }[/math]. Das Spiegelwort entsteht auch aus den gespiegelten Teilen in umgekehrter Reihenfolge: Mit [math]\displaystyle{ v^R = E }[/math] und [math]\displaystyle{ u^R = KK }[/math] ergibt sich [math]\displaystyle{ v^R u^R = EKK }[/math].
- Hängt man an ein Wort [math]\displaystyle{ u }[/math] sein Spiegelwort an, entsteht ein spiegelbildlich aufgebautes Wort [math]\displaystyle{ u\,u^R }[/math]. Für [math]\displaystyle{ u = KE }[/math] ist [math]\displaystyle{ u^R = EK }[/math] und damit [math]\displaystyle{ u\,u^R = KEEK }[/math]: Die zweite Hälfte wiederholt die erste in umgekehrter Reihenfolge.
Akzeptierte und abgelehnte Wörter am Kaffeeautomaten unterscheiden

Der abgebildete Kaffeeautomat besitzt das Eingabealphabet [math]\displaystyle{ \Sigma = \{K; E\} }[/math]. Er sammelt den Kaffeesatz in einem Behälter, dem Satzfach. 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_F }[/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]).
Die Zustandsfolgen dieser Wörter stehen Schritt für Schritt im Beispiel Wortzugehörigkeit mit einem DEA prüfen. Einen Automaten, der das leere Wort akzeptiert, zeigt das Beispiel DEA für Reste entwerfen.