Zum Inhalt springen

Formale Sprache: Unterschied zwischen den Versionen

Aus FLBK-Wiki
Die Seite wurde neu angelegt: „Programme und Maschinen prüfen Eingaben nach festen Regeln. Eine formale Sprache legt genau fest, welche Zeichenfolgen zulässig sind. ==Definition== Eine formale Sprache <math>L</math> über einem Alphabet <math>\Sigma</math> ist eine Teilmenge <math>L \subseteq \Sigma^*</math>. <math>\Sigma^*</math> ist die Menge aller Wörter über <math>\Sigma</math> einschließlich des leeren Wortes. Anders als bei natürlichen Sprachen entscheiden nur…“
 
Keine Bearbeitungszusammenfassung
Zeile 2: Zeile 2:


==Definition==
==Definition==
Eine formale Sprache <math>L</math> über einem [[Alphabet]] <math>\Sigma</math> ist eine Teilmenge <math>L \subseteq \Sigma^*</math>. <math>\Sigma^*</math> ist die Menge aller [[Wort|Wörter]] über <math>\Sigma</math> einschließlich des leeren Wortes. Anders als bei natürlichen Sprachen entscheiden nur die Regeln, die Bedeutung spielt keine Rolle.
Es sei <math>\Sigma</math> ein [[Alphabet]] (eine endliche, nicht leere [[Menge]] von [[Zeichen]]) und <math>\Sigma^*</math> die Menge aller endlichen [[Wort|Wörter]], die sich aus den Zeichen von <math>\Sigma</math> bilden lassen (einschließlich des leeren Wortes <math>\varepsilon</math>).


Für jedes Wort <math>w \in \Sigma^*</math> gilt entweder <math>w \in L</math> oder <math>w \notin L</math>.
Eine '''formale Sprache''' <math>L</math> über dem Alphabet <math>\Sigma</math> ist eine beliebige Teilmenge von <math>\Sigma^*</math>:
 
:<math>L \subseteq \Sigma^*</math>
 
Für eine formale Sprache gelten folgende Grundeigenschaften:
* '''Eindeutige Wortzugehörigkeit:''' Für jedes Wort <math>w \in \Sigma^*</math> gilt eindeutig entweder <math>w \in L</math> (das Wort gehört zur Sprache) oder <math>w \notin L</math> (das Wort gehört nicht zur Sprache).
* '''Formale Regeln statt Bedeutung:''' Anders als bei natürlichen Sprachen entscheiden ausschließlich die formalen Bildungsregeln (die Syntax) über die Zugehörigkeit eines Wortes zu <math>L</math>; eine inhaltliche Bedeutung spielt keine Rolle.
* '''Umfang:''' Eine formale Sprache <math>L</math> kann endlich viele oder unendlich viele Wörter enthalten. Auch die leere Menge <math>L = \emptyset</math> (kein einziges Wort ist gültig) und die Gesamtmenge <math>L = \Sigma^*</math> (jedes Wort über <math>\Sigma</math> ist gültig) sind formale Sprachen.


==Alphabet und Wort==
==Alphabet und Wort==
===Zeichen und Alphabet===
===Zeichen und Alphabet===
Ein [[Zeichen]] ist ein einzelnes Symbol, etwa ein Buchstabe, eine Ziffer oder ein Sonderzeichen. Ein Alphabet <math>\Sigma</math> ist eine endliche, nicht leere Menge von Zeichen. Seine Elemente heißen auch Buchstaben des Alphabets.
Ein [[Zeichen]] ist ein einzelnes, unteilbares Symbol, etwa ein Buchstabe, eine Ziffer oder ein Sonderzeichen. Ein [[Alphabet]] <math>\Sigma</math> ist eine endliche, nicht leere Menge solcher Zeichen (<math>\Sigma \neq \emptyset</math>). Seine Elemente heißen auch Buchstaben des Alphabets.


===Wort und Wortlänge===
===Wort und Wortlänge===
Ein [[Wort]] über <math>\Sigma</math> ist eine endliche Folge von Zeichen aus <math>\Sigma</math>. Die Länge <math>|w|</math> eines Wortes <math>w</math> ist die Anzahl seiner Zeichen.
Ein [[Wort]] <math>w</math> über <math>\Sigma</math> ist eine endliche Folge von Zeichen aus <math>\Sigma</math>. Die Wortlänge <math>|w|</math> eines Wortes <math>w</math> gibt die Anzahl seiner Zeichen an.


Die Verkettung zweier Wörter <math>u</math> und <math>v</math> hängt <math>v</math> an <math>u</math> an und ergibt das Wort <math>uv</math>. Dabei gilt <math>|uv| = |u| + |v|</math>. Die Reihenfolge ist wesentlich: <math>uv</math> und <math>vu</math> sind im Allgemeinen verschiedene Wörter.
Die Verkettung (Konkatenation) zweier Wörter <math>u \in \Sigma^*</math> und <math>v \in \Sigma^*</math> hängt <math>v</math> direkt an <math>u</math> an und ergibt das Wort <math>uv \in \Sigma^*</math>. Dabei addieren sich die Wortlängen: <math>|uv| = |u| + |v|</math>. Die Reihenfolge der Zeichen ist wesentlich: <math>uv</math> und <math>vu</math> sind im Allgemeinen verschiedene Wörter (<math>uv \neq vu</math>).


===Leeres Wort===
===Leeres Wort===
Das leere Wort <math>\varepsilon</math> enthält kein Zeichen, es gilt <math>|\varepsilon| = 0</math>. Es ist ein Wort über jedem Alphabet, gehört aber nicht zum Alphabet. Beim Verketten ändert es nichts: <math>w\varepsilon = \varepsilon w = w</math>.
Das leere Wort <math>\varepsilon</math> enthält kein Zeichen, es gilt <math>|\varepsilon| = 0</math>. Es gehört zu jedem <math>\Sigma^*</math> (<math>\varepsilon \in \Sigma^*</math>), weil es keine Zeichen enthält, die außerhalb von <math>\Sigma</math> liegen, ist aber selbst kein Zeichen des Alphabets (<math>\varepsilon \notin \Sigma</math>). Beim Verketten verändert es ein Wort nicht: <math>w\varepsilon = \varepsilon w = w</math>.


Zwei Sprachen werden leicht verwechselt: Die Sprache <math>\{\varepsilon\}</math> enthält ein Wort, nämlich das leere Wort. Die leere Sprache <math>\emptyset</math> enthält kein Wort.
Zwei spezielle Sprachen werden leicht verwechselt:
* Die Sprache <math>L_1 = \{\varepsilon\}</math> enthält genau '''ein''' Wort, nämlich das leere Wort <math>\varepsilon</math>.
* Die leere Sprache <math>L_2 = \emptyset = \{\}</math> enthält '''kein einziges''' Wort.


==Beschreibung formaler Sprachen==
==Beschreibung formaler Sprachen==
Eine formale Sprache lässt sich auf vier Arten beschreiben:
Eine formale Sprache lässt sich auf vier Arten beschreiben:
* '''Aufzählung:''' Alle Wörter stehen einzeln in einer Menge. Das geht nur bei endlichen Sprachen.
* '''Aufzählung:''' Alle Wörter der Sprache werden einzeln in Mengenklammern aufgelistet. Das ist nur bei endlichen Sprachen möglich.
* '''Mengenschreibweise:''' Eine Bedingung legt fest, welche Wörter zur Sprache gehören, in der Form <math>L = \{w \in \Sigma^* \mid \text{Bedingung}\}</math>. Das geht auch bei unendlichen Sprachen.
* '''Mengenschreibweise:''' Eine mathematische oder sprachliche Bedingung legt fest, welche Wörter zur Sprache gehören, in der Form <math>L = \{w \in \Sigma^* \mid \text{Bedingung an } w\}</math>. Das eignet sich auch für unendliche Sprachen.
* '''Automat:''' Ein [[Endlicher Automat|Automat]] <math>A</math> akzeptiert oder lehnt ein Wort ab. Die Menge aller akzeptierten Wörter ist die Sprache <math>L(A)</math>.
* '''Automat:''' Ein [[Endlicher Automat|Automat]] <math>A</math> prüft ein Eingabewort Schritt für Schritt und akzeptiert es oder lehnt es ab. Die Menge aller von <math>A</math> akzeptierten Wörter ist die Sprache <math>L(A)</math>.
* '''Grammatik:''' Eine [[Formale Grammatik|Grammatik]] <math>G</math> erzeugt Wörter mit Regeln. Die Menge aller erzeugten Wörter ist die Sprache <math>L(G)</math>.
* '''Grammatik:''' Eine [[Formale Grammatik|Grammatik]] <math>G</math> erzeugt Wörter mithilfe von Produktionsregeln. Die Menge aller aus dem Startsymbol ableitbaren Wörter ist die Sprache <math>L(G)</math>.


Die [[Chomsky-Hierarchie]] ordnet die Sprachen nach der Form der Grammatikregeln in Klassen. Jeder Klasse ist ein Automatenmodell zugeordnet, das ihre Sprachen erkennt.
Die [[Chomsky-Hierarchie]] ordnet formale Sprachen nach der Form ihrer Grammatikregeln in vier Klassen ein. Jeder Klasse ist ein passendes Automatenmodell zugeordnet, das genau die Sprachen dieser Klasse erkennt.


==Beispiele==
==Beispiele==
===Sprache als Menge angeben===
===Sprache als Menge angeben===
[[Datei:DEA Kaffeeautomat vollständig.png|mini|Vollständiger DEA des Kaffeeautomaten]]
[[Datei:DEA Kaffeeautomat vollständig.png|mini|Vollständiger DEA des Kaffeeautomaten]]
Ein Kaffeeautomat sammelt den Kaffeesatz in einem Satzfach. Das Satzfach ist bei genau vier Einheiten voll. Ein Kaffee K zählt 1 Einheit, ein Espresso E zählt 2 Einheiten. Das Eingabealphabet ist <math>\Sigma = \{K, E\}</math>.
Ein Kaffeeautomat sammelt den Kaffeesatz in einem Satzfach. Das Satzfach ist bei genau 4 Einheiten voll. Ein Kaffee <math>K</math> zählt 1 Einheit, ein Espresso <math>E</math> zählt 2 Einheiten. Das Eingabealphabet lautet <math>\Sigma = \{K, E\}</math>.
 
Gesucht ist die formale Sprache <math>L \subseteq \Sigma^*</math> aller Tastenkombinationen, die das Satzfach ohne Überlauf exakt füllen. In Mengenschreibweise lautet die Sprache:
 
:<math>L = \{w \in \{K, E\}^* \mid \text{Die Summe der Einheiten in } w \text{ beträgt genau } 4\}</math>


Ein Wort gehört zur Sprache, wenn es das Satzfach genau füllt, also zusammen 4 Einheiten ergibt. Fünf Wörter erfüllen das:
Ein Wort gehört genau dann zu <math>L</math>, wenn sich die Einheiten seiner Zeichen zu 4 addieren. Genau fünf Wörter aus <math>\Sigma^*</math> erfüllen diese Bedingung:


{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
! Wort !! Einheiten
! Wort <math>w</math> !! Wortlänge <math>|w|</math> !! Berechnung der Einheiten
|-
|-
| KKKK || 1 + 1 + 1 + 1 = 4
| <math>KKKK</math> || 4 || <math>1 + 1 + 1 + 1 = 4</math>
|-
|-
| EE || 2 + 2 = 4
| <math>EE</math> || 2 || <math>2 + 2 = 4</math>
|-
|-
| EKK || 2 + 1 + 1 = 4
| <math>EKK</math> || 3 || <math>2 + 1 + 1 = 4</math>
|-
|-
| KEK || 1 + 2 + 1 = 4
| <math>KEK</math> || 3 || <math>1 + 2 + 1 = 4</math>
|-
|-
| KKE || 1 + 1 + 2 = 4
| <math>KKE</math> || 3 || <math>1 + 1 + 2 = 4</math>
|}
|}


Die Sprache ist endlich, deshalb genügt die Aufzählung:
Da die Sprache endlich ist, lässt sie sich vollständig durch Aufzählung ihrer fünf Elemente angeben:


:<math>L = \{KKKK, EE, EKK, KEK, KKE\}</math>
:<math>L = \{KKKK, EE, EKK, KEK, KKE\}</math>


Alle anderen Wörter über <math>\Sigma</math> gehören nicht zu <math>L</math>. Der Automat im Bild akzeptiert genau die Wörter von <math>L</math>. Sein Aufbau steht im Beispiel [[Deterministischer endlicher Automat#Kaffeeautomat als vollständigen DEA angeben|Kaffeeautomat als vollständigen DEA angeben]].
Alle anderen Wörter über <math>\Sigma</math> gehören nicht zu <math>L</math>. Der im Bild dargestellte Automat akzeptiert mit seinem Endzustand <math>q_4</math> genau die Wörter von <math>L</math>. Sein Aufbau wird im Beispiel [[Deterministischer endlicher Automat#Kaffeeautomat als vollständigen DEA angeben|Kaffeeautomat als vollständigen DEA angeben]] hergeleitet.


===Wortzugehörigkeit prüfen===
===Wortzugehörigkeit prüfen===
Ob ein Wort zur Sprache <math>L</math> aus dem vorigen Beispiel gehört, zeigt die Summe seiner Einheiten. Sie muss genau 4 betragen.
Ob ein Wort <math>w \in \Sigma^*</math> zur Sprache <math>L = \{KKKK, EE, EKK, KEK, KKE\}</math> aus dem vorigen Beispiel gehört, entscheidet die Summe seiner Kaffeesatz-Einheiten (sie muss exakt 4 betragen):


* <math>KEK \in L</math>: 1 + 2 + 1 = 4 Einheiten. Das Satzfach ist genau voll. Die Länge ist <math>|KEK| = 3</math>.
* '''<math>KEK \in L</math>:''' Das Wort besteht aus drei Zeichen (<math>|KEK| = 3</math>) und liefert <math>1 + 2 + 1 = 4</math> Einheiten. Das Satzfach ist genau voll (der Automat endet im Endzustand <math>q_4</math>), also gehört <math>KEK</math> zur Sprache <math>L</math>.
* <math>EEK \notin L</math>: 2 + 2 + 1 = 5 Einheiten. Das Satzfach läuft über.
* '''<math>EEK \notin L</math>:''' Das Wort hat die Länge <math>|EEK| = 3</math> und liefert <math>2 + 2 + 1 = 5</math> Einheiten. Das Satzfach läuft über (der Automat wechselt in den Fehlerzustand <math>q_5</math>), also gehört <math>EEK</math> nicht zu <math>L</math>.
* <math>KK \notin L</math>: 1 + 1 = 2 Einheiten. Das Satzfach ist nicht voll.
* '''<math>KK \notin L</math>:''' Das Wort hat die Länge <math>|KK| = 2</math> und liefert <math>1 + 1 = 2</math> Einheiten. Das Satzfach ist noch nicht voll (der Automat bleibt im Zustand <math>q_2</math> stehen), also gehört <math>KK</math> nicht zu <math>L</math>.
* <math>\varepsilon \notin L</math>: Das leere Wort hat 0 Einheiten, es gilt <math>|\varepsilon| = 0</math>. Das Satzfach bleibt leer.
* '''<math>\varepsilon \notin L</math>:''' Das leere Wort enthält kein Zeichen (<math>|\varepsilon| = 0</math>) und liefert 0 Einheiten. Das Satzfach bleibt leer (der Automat verbleibt im Startzustand <math>q_0</math>). Es gilt zwar <math>\varepsilon \in \Sigma^*</math>, aber <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:11 Uhr

Programme und Maschinen prüfen Eingaben nach festen Regeln. Eine formale Sprache legt genau fest, welche Zeichenfolgen zulässig sind.

Definition

Es sei [math]\displaystyle{ \Sigma }[/math] ein Alphabet (eine endliche, nicht leere Menge von Zeichen) und [math]\displaystyle{ \Sigma^* }[/math] die Menge aller endlichen Wörter, die sich aus den Zeichen von [math]\displaystyle{ \Sigma }[/math] bilden lassen (einschließlich des leeren Wortes [math]\displaystyle{ \varepsilon }[/math]).

Eine formale Sprache [math]\displaystyle{ L }[/math] über dem Alphabet [math]\displaystyle{ \Sigma }[/math] ist eine beliebige Teilmenge von [math]\displaystyle{ \Sigma^* }[/math]:

[math]\displaystyle{ L \subseteq \Sigma^* }[/math]

Für eine formale Sprache gelten folgende Grundeigenschaften:

  • Eindeutige Wortzugehörigkeit: Für jedes Wort [math]\displaystyle{ w \in \Sigma^* }[/math] gilt eindeutig entweder [math]\displaystyle{ w \in L }[/math] (das Wort gehört zur Sprache) oder [math]\displaystyle{ w \notin L }[/math] (das Wort gehört nicht zur Sprache).
  • Formale Regeln statt Bedeutung: Anders als bei natürlichen Sprachen entscheiden ausschließlich die formalen Bildungsregeln (die Syntax) über die Zugehörigkeit eines Wortes zu [math]\displaystyle{ L }[/math]; eine inhaltliche Bedeutung spielt keine Rolle.
  • Umfang: Eine formale Sprache [math]\displaystyle{ L }[/math] kann endlich viele oder unendlich viele Wörter enthalten. Auch die leere Menge [math]\displaystyle{ L = \emptyset }[/math] (kein einziges Wort ist gültig) und die Gesamtmenge [math]\displaystyle{ L = \Sigma^* }[/math] (jedes Wort über [math]\displaystyle{ \Sigma }[/math] ist gültig) sind formale Sprachen.

Alphabet und Wort

Zeichen und Alphabet

Ein Zeichen ist ein einzelnes, unteilbares Symbol, etwa ein Buchstabe, eine Ziffer oder ein Sonderzeichen. Ein Alphabet [math]\displaystyle{ \Sigma }[/math] ist eine endliche, nicht leere Menge solcher Zeichen ([math]\displaystyle{ \Sigma \neq \emptyset }[/math]). Seine Elemente heißen auch Buchstaben des Alphabets.

Wort und Wortlänge

Ein Wort [math]\displaystyle{ w }[/math] über [math]\displaystyle{ \Sigma }[/math] ist eine endliche Folge von Zeichen aus [math]\displaystyle{ \Sigma }[/math]. Die Wortlänge [math]\displaystyle{ |w| }[/math] eines Wortes [math]\displaystyle{ w }[/math] gibt die Anzahl seiner Zeichen an.

Die Verkettung (Konkatenation) zweier Wörter [math]\displaystyle{ u \in \Sigma^* }[/math] und [math]\displaystyle{ v \in \Sigma^* }[/math] hängt [math]\displaystyle{ v }[/math] direkt an [math]\displaystyle{ u }[/math] an und ergibt das Wort [math]\displaystyle{ uv \in \Sigma^* }[/math]. Dabei addieren sich die Wortlängen: [math]\displaystyle{ |uv| = |u| + |v| }[/math]. Die Reihenfolge der Zeichen ist wesentlich: [math]\displaystyle{ uv }[/math] und [math]\displaystyle{ vu }[/math] sind im Allgemeinen verschiedene Wörter ([math]\displaystyle{ uv \neq vu }[/math]).

Leeres Wort

Das leere Wort [math]\displaystyle{ \varepsilon }[/math] enthält kein Zeichen, es gilt [math]\displaystyle{ |\varepsilon| = 0 }[/math]. Es gehört zu jedem [math]\displaystyle{ \Sigma^* }[/math] ([math]\displaystyle{ \varepsilon \in \Sigma^* }[/math]), weil es keine Zeichen enthält, die außerhalb von [math]\displaystyle{ \Sigma }[/math] liegen, ist aber selbst kein Zeichen des Alphabets ([math]\displaystyle{ \varepsilon \notin \Sigma }[/math]). Beim Verketten verändert es ein Wort nicht: [math]\displaystyle{ w\varepsilon = \varepsilon w = w }[/math].

Zwei spezielle Sprachen werden leicht verwechselt:

  • Die Sprache [math]\displaystyle{ L_1 = \{\varepsilon\} }[/math] enthält genau ein Wort, nämlich das leere Wort [math]\displaystyle{ \varepsilon }[/math].
  • Die leere Sprache [math]\displaystyle{ L_2 = \emptyset = \{\} }[/math] enthält kein einziges Wort.

Beschreibung formaler Sprachen

Eine formale Sprache lässt sich auf vier Arten beschreiben:

  • Aufzählung: Alle Wörter der Sprache werden einzeln in Mengenklammern aufgelistet. Das ist nur bei endlichen Sprachen möglich.
  • Mengenschreibweise: Eine mathematische oder sprachliche Bedingung legt fest, welche Wörter zur Sprache gehören, in der Form [math]\displaystyle{ L = \{w \in \Sigma^* \mid \text{Bedingung an } w\} }[/math]. Das eignet sich auch für unendliche Sprachen.
  • Automat: Ein Automat [math]\displaystyle{ A }[/math] prüft ein Eingabewort Schritt für Schritt und akzeptiert es oder lehnt es ab. Die Menge aller von [math]\displaystyle{ A }[/math] akzeptierten Wörter ist die Sprache [math]\displaystyle{ L(A) }[/math].
  • Grammatik: Eine Grammatik [math]\displaystyle{ G }[/math] erzeugt Wörter mithilfe von Produktionsregeln. Die Menge aller aus dem Startsymbol ableitbaren Wörter ist die Sprache [math]\displaystyle{ L(G) }[/math].

Die Chomsky-Hierarchie ordnet formale Sprachen nach der Form ihrer Grammatikregeln in vier Klassen ein. Jeder Klasse ist ein passendes Automatenmodell zugeordnet, das genau die Sprachen dieser Klasse erkennt.

Beispiele

Sprache als Menge angeben

Vollständiger DEA des Kaffeeautomaten

Ein Kaffeeautomat sammelt den Kaffeesatz in einem Satzfach. Das Satzfach ist bei genau 4 Einheiten voll. Ein Kaffee [math]\displaystyle{ K }[/math] zählt 1 Einheit, ein Espresso [math]\displaystyle{ E }[/math] zählt 2 Einheiten. Das Eingabealphabet lautet [math]\displaystyle{ \Sigma = \{K, E\} }[/math].

Gesucht ist die formale Sprache [math]\displaystyle{ L \subseteq \Sigma^* }[/math] aller Tastenkombinationen, die das Satzfach ohne Überlauf exakt füllen. In Mengenschreibweise lautet die Sprache:

[math]\displaystyle{ L = \{w \in \{K, E\}^* \mid \text{Die Summe der Einheiten in } w \text{ beträgt genau } 4\} }[/math]

Ein Wort gehört genau dann zu [math]\displaystyle{ L }[/math], wenn sich die Einheiten seiner Zeichen zu 4 addieren. Genau fünf Wörter aus [math]\displaystyle{ \Sigma^* }[/math] erfüllen diese Bedingung:

Wort [math]\displaystyle{ w }[/math] Wortlänge [math]\displaystyle{ |w| }[/math] Berechnung der Einheiten
[math]\displaystyle{ KKKK }[/math] 4 [math]\displaystyle{ 1 + 1 + 1 + 1 = 4 }[/math]
[math]\displaystyle{ EE }[/math] 2 [math]\displaystyle{ 2 + 2 = 4 }[/math]
[math]\displaystyle{ EKK }[/math] 3 [math]\displaystyle{ 2 + 1 + 1 = 4 }[/math]
[math]\displaystyle{ KEK }[/math] 3 [math]\displaystyle{ 1 + 2 + 1 = 4 }[/math]
[math]\displaystyle{ KKE }[/math] 3 [math]\displaystyle{ 1 + 1 + 2 = 4 }[/math]

Da die Sprache endlich ist, lässt sie sich vollständig durch Aufzählung ihrer fünf Elemente angeben:

[math]\displaystyle{ L = \{KKKK, EE, EKK, KEK, KKE\} }[/math]

Alle anderen Wörter über [math]\displaystyle{ \Sigma }[/math] gehören nicht zu [math]\displaystyle{ L }[/math]. Der im Bild dargestellte Automat akzeptiert mit seinem Endzustand [math]\displaystyle{ q_4 }[/math] genau die Wörter von [math]\displaystyle{ L }[/math]. Sein Aufbau wird im Beispiel Kaffeeautomat als vollständigen DEA angeben hergeleitet.

Wortzugehörigkeit prüfen

Ob ein Wort [math]\displaystyle{ w \in \Sigma^* }[/math] zur Sprache [math]\displaystyle{ L = \{KKKK, EE, EKK, KEK, KKE\} }[/math] aus dem vorigen Beispiel gehört, entscheidet die Summe seiner Kaffeesatz-Einheiten (sie muss exakt 4 betragen):

  • [math]\displaystyle{ KEK \in L }[/math]: Das Wort besteht aus drei Zeichen ([math]\displaystyle{ |KEK| = 3 }[/math]) und liefert [math]\displaystyle{ 1 + 2 + 1 = 4 }[/math] Einheiten. Das Satzfach ist genau voll (der Automat endet im Endzustand [math]\displaystyle{ q_4 }[/math]), also gehört [math]\displaystyle{ KEK }[/math] zur Sprache [math]\displaystyle{ L }[/math].
  • [math]\displaystyle{ EEK \notin L }[/math]: Das Wort hat die Länge [math]\displaystyle{ |EEK| = 3 }[/math] und liefert [math]\displaystyle{ 2 + 2 + 1 = 5 }[/math] Einheiten. Das Satzfach läuft über (der Automat wechselt in den Fehlerzustand [math]\displaystyle{ q_5 }[/math]), also gehört [math]\displaystyle{ EEK }[/math] nicht zu [math]\displaystyle{ L }[/math].
  • [math]\displaystyle{ KK \notin L }[/math]: Das Wort hat die Länge [math]\displaystyle{ |KK| = 2 }[/math] und liefert [math]\displaystyle{ 1 + 1 = 2 }[/math] Einheiten. Das Satzfach ist noch nicht voll (der Automat bleibt im Zustand [math]\displaystyle{ q_2 }[/math] stehen), also gehört [math]\displaystyle{ KK }[/math] nicht zu [math]\displaystyle{ L }[/math].
  • [math]\displaystyle{ \varepsilon \notin L }[/math]: Das leere Wort enthält kein Zeichen ([math]\displaystyle{ |\varepsilon| = 0 }[/math]) und liefert 0 Einheiten. Das Satzfach bleibt leer (der Automat verbleibt im Startzustand [math]\displaystyle{ q_0 }[/math]). Es gilt zwar [math]\displaystyle{ \varepsilon \in \Sigma^* }[/math], aber [math]\displaystyle{ \varepsilon \notin L }[/math].