Wort: Unterschied zwischen den Versionen
Thomas (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Keine Bearbeitungszusammenfassung |
||
| (3 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| 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. | |||
Es | ==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> | ||
[[ | |||
Die vom | <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== | |||
===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== | |||
===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" | |||
! Potenzschreibweise !! ausgeschrieben !! Wortlänge | |||
|- | |||
| <math>K^3</math> || <math>KKK</math> || <math>3 \cdot 1 = 3</math> | |||
|- | |||
| <math>(KE)^2</math> || <math>KEKE</math> || <math>2 \cdot 2 = 4</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" | |||
! Menge !! ausgeschrieben !! Anzahl der Wörter | |||
|- | |||
| <math>\Sigma^0</math> || <math>\{\varepsilon\}</math> || <math>2^0 = 1</math> | |||
|- | |||
| <math>\Sigma^1</math> || <math>\{K; E\}</math> || <math>2^1 = 2</math> | |||
|- | |||
| <math>\Sigma^2</math> || <math>\{KK; KE; EK; EE\}</math> || <math>2^2 = 4</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:Formale Sprachen]] | |||
[[Kategorie:AHR I Informatik LK]] | |||