Formale Sprache: Unterschied zwischen den Versionen

Keine Bearbeitungszusammenfassung
Markierung: Zurückgesetzt
Keine Bearbeitungszusammenfassung
Markierung: Manuelle Zurücksetzung
 
Zeile 1: Zeile 1:
Ein Kellerautomat ist ein [[Endlicher Automat|endlicher Automat]] mit zusätzlichem Speicher. Damit kann er verschachtelte Strukturen wie Klammern prüfen.
Programme und Maschinen prüfen Eingaben nach festen Regeln. Eine formale Sprache legt genau fest, welche Zeichenfolgen zulässig sind.


==Definition==
==Definition==
Ein '''Kellerautomat''' ist ein 7-Tupel <math>M = (Q; \Sigma; \Gamma; \delta; q_0; \#; F)</math>. Wie beim endlichen Automaten ist <math>Q</math> die endliche, nicht leere Zustandsmenge, <math>\Sigma</math> das [[Alphabet|Eingabealphabet]], <math>\delta</math> die Übergangsfunktion (siehe [[#Formale Darstellung|Formale Darstellung]]), <math>q_0 \in Q</math> der Startzustand und <math>F \subseteq Q</math> die Menge der Endzustände. Zusätzlich besitzt der Kellerautomat:
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>).


* das Kelleralphabet <math>\Gamma</math>, die Menge der [[Zeichen]], die im Keller liegen dürfen. Diese Zeichen heißen Kellerzeichen.
Eine '''formale Sprache''' <math>L</math> über dem Alphabet <math>\Sigma</math> ist eine beliebige [[Menge#Teilmenge|Teilmenge]] von <math>\Sigma^*</math>:
* das Kellerbodensymbol <math>\# \in \Gamma</math>, das zu Beginn als einziges Zeichen im Keller liegt. Es gehört selbst zu den Kellerzeichen.


Der Keller ist ein unbegrenzter Speicher: Er kann beliebig viele Zeichen aufnehmen. Er arbeitet nach dem LIFO-Prinzip (last in, first out) wie ein [[Stapel]]. Der Automat sieht nur das oberste Zeichen. Das zuletzt abgelegte Zeichen wird als Erstes wieder entfernt. Das Kellerbodensymbol markiert den Boden: Liegt es oben, weiß der Automat, dass kein anderes Zeichen mehr im Keller ist.
:<math>L \subseteq \Sigma^*</math>


==Arbeitsweise==
Für eine formale Sprache gelten folgende Grundeigenschaften:
Ein Schritt hängt vom Zustand, vom nächsten Eingabezeichen und vom obersten Kellerzeichen ab. Diese drei Angaben bilden die Lage des Automaten. Der Automat wechselt den Zustand und ersetzt das oberste Kellerzeichen durch ein [[Wort]] aus Kellerzeichen, das Ersatzwort. Je nach Ersatzwort wirkt der Schritt so auf den Keller:
* '''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 (die Semantik) 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.


* Ablegen: Das Ersatzwort besteht aus dem bisherigen obersten Zeichen und einem weiteren Zeichen. Der Keller wird höher.
==Alphabet und Wort==
* Entfernen: Das Ersatzwort ist leer. Das oberste Zeichen verschwindet. Das leere Ersatzwort wird <math>\varepsilon</math> geschrieben.
===Zeichen und Alphabet===
* Unverändert lassen: Das Ersatzwort besteht nur aus dem bisherigen obersten Zeichen.
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.


Eine Ausnahme ist der <math>\varepsilon</math>-Übergang: Bei ihm liest der Automat kein Eingabezeichen. Die Eingabe bleibt stehen, nur Zustand und Keller ändern sich. Der Automat führt ihn aus, sobald Zustand und oberstes Kellerzeichen passen. Das nächste Eingabezeichen spielt dabei keine Rolle.
===Wort und Wortlänge===
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.


Ein Kellerautomat ist '''deterministisch''', wenn in jeder Lage höchstens ein Übergang möglich ist. Für einen Zustand und ein oberstes Kellerzeichen gibt es dann entweder Übergänge mit Eingabezeichen oder einen <math>\varepsilon</math>-Übergang, nie beides. Nichtdeterministische Kellerautomaten dürfen wie ein [[Nichtdeterministischer endlicher Automat|NEA]] mehrere Möglichkeiten offenhalten.
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>).


==Akzeptanz==
===Leeres Wort===
Der Kellerautomat akzeptiert ein Wort, wenn die Eingabe vollständig gelesen ist und er in einem Endzustand steht. Mögliche <math>\varepsilon</math>-Übergänge am Ende der Eingabe werden vorher noch ausgeführt. Gibt es in einer Lage keinen passenden Übergang, obwohl noch Eingabe übrig ist, bricht der Automat ab und lehnt das Wort ab.
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>.


Was am Ende noch im Keller liegt, spielt für diese Akzeptanz keine Rolle. Soll der Automat ein Wort nur dann akzeptieren, wenn alle abgelegten Zeichen wieder entfernt sind, muss er das über seine Zustände sicherstellen: Er darf nur dann in einem Endzustand stehen, wenn im Keller nur noch das Kellerbodensymbol <math>\#</math> liegt. Im [[#Klammerausdruck mit einem Keller prüfen|ersten Beispiel]] führt deshalb nur ein <math>\varepsilon</math>-Übergang in den Endzustand zurück, der <math>\#</math> oben verlangt und den Keller unverändert lässt.
Zwei spezielle Sprachen werden leicht verwechselt:
* Die Sprache <math>\{\varepsilon\}</math> enthält genau '''ein''' Wort, nämlich das leere Wort <math>\varepsilon</math>.
* Die leere Sprache <math>\emptyset = \{\}</math> enthält '''kein einziges''' Wort.


Andere Quellen akzeptieren stattdessen bei leerem Keller. Anders als bei endlichen Automaten leisten nichtdeterministische Kellerautomaten mehr als deterministische: Sie erkennen alle [[Kontextfreie Grammatik|kontextfreien Sprachen]], deterministische Kellerautomaten nur einen Teil davon.
==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 und durch Semikolons getrennt. 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>L = \{w \in \Sigma^* \mid \text{Bedingung an } w\}</math>. Der senkrechte Strich wird „für die gilt“ gelesen. Das eignet sich auch für unendliche Sprachen. Vor dem Strich kann statt <math>w</math> auch ein Wortmuster stehen, das den Aufbau der Wörter zeigt, zum Beispiel mit einer [[Wort#Wortpotenz|Wortpotenz]] oder mit einem Platzhalter für ein beliebiges Wort. Hinter dem Strich steht dann, welche Werte die Variablen annehmen dürfen.
* '''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 mithilfe von Produktionsregeln. Die Menge aller aus dem Startsymbol ableitbaren Wörter ist die Sprache <math>L(G)</math>.


==Formale Darstellung==
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.
Die Übergangsfunktion eines deterministischen Kellerautomaten hat die Form <math>\delta: Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to Q \times \Gamma^*</math>. Sie ordnet dem Zustand, dem Eingabezeichen (oder <math>\varepsilon</math>) und dem obersten Kellerzeichen einen Folgezustand und ein Ersatzwort zu. <math>\Gamma^*</math> ist die Menge aller Wörter aus Kellerzeichen einschließlich des leeren Wortes <math>\varepsilon</math>, siehe [[Wort#Definition|Kleenesche Hülle]]. Die Übergangsfunktion muss nicht für jede Lage einen Wert haben.


In der Tabelle steht jede Zeile für einen Übergang. Die Spalten heißen Zustand, Eingabe, oben im Keller, Folgezustand und ersetzt durch. Die Spalte „oben im Keller“ nennt das oberste Kellerzeichen, die Spalte „ersetzt durch“ das Ersatzwort. Ein Ersatzwort wird von links nach rechts geschrieben, sein letztes Zeichen liegt danach oben. Für Lagen, die in der Tabelle fehlen, gibt es keinen Übergang.
==Sprachen als Mengen==
 
Weil formale Sprachen [[Menge|Mengen]] von Wörtern sind, gelten für sie alle Begriffe der Mengenlehre:
==Anwendung und Grenzen==
* '''Endlich oder unendlich:''' Eine Sprache ist endlich, wenn sie nur endlich viele Wörter enthält. Enthält eine Sprache mindestens ein Wort und gibt es zu jedem ihrer Wörter ein längeres Wort, das ebenfalls zur Sprache gehört, ist sie unendlich.
Ein [[Compiler]] arbeitet beim Prüfen eines Programms wie ein Kellerautomat: Er legt für jede geöffnete Klammer und jeden begonnenen Block einen Eintrag auf einem Stapel ab und entfernt den obersten Eintrag, sobald die passende schließende Klammer folgt. Passt sie nicht oder bleibt am Ende ein Eintrag übrig, meldet er einen [[Syntax|Syntaxfehler]].
* '''Teilmenge:''' <math>L_1 \subseteq L_2</math> gilt, wenn jedes Wort aus <math>L_1</math> auch zu <math>L_2</math> gehört. Um zu zeigen, dass diese Beziehung '''nicht''' gilt, genügt ein einziges Wort aus <math>L_1</math>, das nicht in <math>L_2</math> liegt (ein Gegenbeispiel).
 
* '''Schnitt und Vereinigung:''' Die [[Menge#Schnittmenge|Schnittmenge]] <math>L_1 \cap L_2</math> enthält die Wörter, die zu beiden Sprachen gehören. Die [[Menge#Vereinigungsmenge|Vereinigungsmenge]] <math>L_1 \cup L_2</math> enthält die Wörter, die zu mindestens einer der beiden Sprachen gehören.
Mit dem Keller kann ein Automat zwei Anzahlen vergleichen: Er legt für jedes Zeichen des ersten Blocks ein Kellerzeichen ab und entfernt für jedes Zeichen des zweiten Blocks eines. Auch mehrere solche Vergleiche gelingen, wenn sie nacheinander stattfinden oder ineinander verschachtelt sind. Dieselbe Anzahl ein zweites Mal zu vergleichen gelingt nicht: Nach dem ersten Vergleich sind die abgelegten Zeichen entfernt, und die Anzahl ist verloren. Drei gleich lange Blöcke wie in der Sprache <math>\{a^n b^n c^n \mid n \geq 1\}</math> erkennt deshalb kein Kellerautomat, siehe [[Chomsky-Hierarchie#Sprachen einordnen|Sprachen einordnen]].


==Beispiele==
==Beispiele==
===Klammerausdruck mit einem Keller prüfen===
===Sprache als Menge angeben===
Der Kellerautomat prüft, ob jede öffnende Klammer eine passende schließende hat. Als 7-Tupel <math>M = (Q; \Sigma; \Gamma; \delta; q_0; \#; F)</math> hat er diese Bestandteile:
[[Datei:DEA Kaffeeautomat vollständig.png|mini|Vollständiger DEA des Kaffeeautomaten]]
* <math>Q = \{q_0; q_1\}</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>.
* <math>\Sigma = \{(; )\}</math>
* <math>\Gamma = \{\#; K\}</math>
* Startzustand <math>q_0</math> und Kellerbodensymbol <math>\#</math>
* <math>F = \{q_0\}</math>


In <math>q_0</math> sind alle bisher geöffneten Klammern wieder geschlossen. In <math>q_1</math> liest der Automat einen begonnenen Klammerausdruck. Jede öffnende Klammer legt ein <math>K</math> ab, jede schließende Klammer entfernt ein <math>K</math>. Liegt in <math>q_1</math> nur noch <math>\#</math> im Keller, wechselt der Automat ohne Eingabezeichen zurück nach <math>q_0</math>. Die Übergangsfunktion <math>\delta</math> steht in der Tabelle:
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:


{| class="wikitable" style="text-align:center"
:<math>L = \{w \in \{K; E\}^* \mid \text{Die Summe der Einheiten in } w \text{ beträgt genau } 4\}</math>
! Zustand !! Eingabe !! oben im Keller !! Folgezustand !! ersetzt durch
|-
| <math>q_0</math> || <math>(</math> || <math>\#</math> || <math>q_1</math> || <math>\#K</math>
|-
| <math>q_1</math> || <math>(</math> || <math>K</math> || <math>q_1</math> || <math>KK</math>
|-
| <math>q_1</math> || <math>)</math> || <math>K</math> || <math>q_1</math> || <math>\varepsilon</math>
|-
| <math>q_1</math> || <math>\varepsilon</math> || <math>\#</math> || <math>q_0</math> || <math>\#</math>
|}


Der Keller wird von links nach rechts geschrieben, oben steht rechts. Das Protokoll zeigt den Lauf für <math>(())</math>. Zu Beginn liegt nur <math>\#</math> im Keller.
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"
! Schritt !! Zustand !! Resteingabe !! Keller (oben rechts)
! Wort <math>w</math> !! Wortlänge <math>|w|</math> !! Berechnung der Einheiten
|-
|-
| 0 || <math>q_0</math> || <math>(())</math> || <math>\#</math>
| <math>KKKK</math> || 4 || <math>1 + 1 + 1 + 1 = 4</math>
|-
|-
| 1 || <math>q_1</math> || <math>())</math> || <math>\#K</math>
| <math>EE</math> || 2 || <math>2 + 2 = 4</math>
|-
|-
| 2 || <math>q_1</math> || <math>))</math> || <math>\#KK</math>
| <math>EKK</math> || 3 || <math>2 + 1 + 1 = 4</math>
|-
|-
| 3 || <math>q_1</math> || <math>)</math> || <math>\#K</math>
| <math>KEK</math> || 3 || <math>1 + 2 + 1 = 4</math>
|-
|-
| 4 || <math>q_1</math> || <math>\varepsilon</math> || <math>\#</math>
| <math>KKE</math> || 3 || <math>1 + 1 + 2 = 4</math>
|-
| 5 || <math>q_0</math> || <math>\varepsilon</math> || <math>\#</math>
|}
|}


[[Datei:Kellerbelegung Klammerausdruck.png|mini|Kellerbelegung beim Lesen von (())]]
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>


In Schritt 1 liest der Automat die erste öffnende Klammer, legt ein <math>K</math> auf <math>\#</math> und wechselt nach <math>q_1</math>. In Schritt 2 legt die zweite öffnende Klammer ein weiteres <math>K</math> ab. In den Schritten 3 und 4 entfernt jede schließende Klammer ein <math>K</math>. Danach liegt nur noch <math>\#</math> im Keller. Schritt 5 ist der <math>\varepsilon</math>-Übergang: Er führt ohne Eingabezeichen nach <math>q_0</math>. Am Ende ist alles gelesen, und <math>q_0</math> ist ein Endzustand. Der Automat akzeptiert <math>(())</math>.
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.


===Abgelehntes Wort protokollieren===
===Wortzugehörigkeit prüfen===
Das Protokoll für <math>(()</math> zeigt, warum der Automat dieses Wort ablehnt.
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):


{| class="wikitable" style="text-align:center"
* '''<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>.
! Schritt !! Zustand !! Resteingabe !! Keller (oben rechts)
* '''<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 [[Deterministischer endlicher Automat#Vollständiger DEA und Fehlerzustand|Fehlerzustand]] <math>q_F</math>), also gehört <math>EEK</math> nicht zu <math>L</math>.
|-
* '''<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>.
| 0 || <math>q_0</math> || <math>(()</math> || <math>\#</math>
* '''<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>.
|-
| 1 || <math>q_1</math> || <math>()</math> || <math>\#K</math>
|-
| 2 || <math>q_1</math> || <math>)</math> || <math>\#KK</math>
|-
| 3 || <math>q_1</math> || <math>\varepsilon</math> || <math>\#K</math>
|}


Alles ist gelesen, aber ein <math>K</math> liegt noch im Keller. Der Automat steht in <math>q_1</math>, und <math>q_1</math> ist kein Endzustand. Für <math>q_1</math> mit <math>K</math> oben gibt es keinen <math>\varepsilon</math>-Übergang, der Automat bleibt dort stehen. Er lehnt <math>(()</math> ab.
===Zeichenfolge außerhalb des Alphabets erkennen===
Eine Zeichenfolge kann aus zwei verschiedenen Gründen nicht zu einer Sprache gehören. Für die Sprache <math>L</math> des Kaffeeautomaten über <math>\Sigma = \{K; E\}</math> zeigt das der Vergleich zweier Eingaben:


Über die Akzeptanz entscheidet dabei der Zustand, nicht der Keller: Wäre auch <math>q_1</math> ein Endzustand, würde der Automat <math>(()</math> akzeptieren, obwohl noch ein <math>K</math> im Keller liegt.
* '''<math>KTE</math>:''' Das Zeichen <math>T</math> gehört nicht zum Alphabet (<math>T \notin \Sigma</math>). Die Zeichenfolge ist deshalb gar kein Wort über <math>\Sigma</math> (<math>KTE \notin \Sigma^*</math>) und kann zu keiner Sprache über <math>\Sigma</math> gehören.
* '''<math>KK</math>:''' Alle Zeichen stammen aus dem Alphabet, es gilt <math>KK \in \Sigma^*</math>. Das Wort erfüllt aber die Regel der Sprache nicht, weil es nur 2 Einheiten liefert. Deshalb gilt <math>KK \notin L</math>.


===ε-Übergang mitten in der Eingabe verfolgen===
Zuerst wird also geprüft, ob alle Zeichen zum Alphabet gehören, danach, ob das Wort die Regel der Sprache erfüllt.
Das Wort <math>()()</math> besteht aus zwei Klammerpaaren nacheinander. Der Automat aus dem ersten Beispiel führt den <math>\varepsilon</math>-Übergang hier zweimal aus:


{| class="wikitable" style="text-align:center"
===Unendliche Sprache in Mengenschreibweise angeben===
! Schritt !! Zustand !! Resteingabe !! Keller (oben rechts)
Gesucht ist die Sprache <math>L_E</math> aller Bestellfolgen über <math>\Sigma = \{K; E\}</math>, die mindestens einen Espresso enthalten.
|-
| 0 || <math>q_0</math> || <math>()()</math> || <math>\#</math>
|-
| 1 || <math>q_1</math> || <math>)()</math> || <math>\#K</math>
|-
| 2 || <math>q_1</math> || <math>()</math> || <math>\#</math>
|-
| 3 || <math>q_0</math> || <math>()</math> || <math>\#</math>
|-
| 4 || <math>q_1</math> || <math>)</math> || <math>\#K</math>
|-
| 5 || <math>q_1</math> || <math>\varepsilon</math> || <math>\#</math>
|-
| 6 || <math>q_0</math> || <math>\varepsilon</math> || <math>\#</math>
|}


Nach dem ersten Klammerpaar liegt in Schritt 2 nur noch <math>\#</math> im Keller. In <math>q_1</math> mit <math>\#</math> oben gibt es nur den <math>\varepsilon</math>-Übergang, also führt der Automat ihn in Schritt 3 aus, obwohl noch Eingabe übrig ist. Zurück in <math>q_0</math> kann er die nächste öffnende Klammer lesen. Am Ende ist alles gelesen, und der Automat steht im Endzustand <math>q_0</math>: Er akzeptiert <math>()()</math>.
* '''Mit einer Bedingung:''' <math>L_E = \{w \in \Sigma^* \mid w \text{ enthält mindestens ein } E\}</math>
* '''Mit einem Wortmuster:''' <math>L_E = \{uEv \mid u \in \Sigma^* \text{ und } v \in \Sigma^*\}</math>. Die Platzhalter <math>u</math> und <math>v</math> stehen für beliebige Wörter über <math>\Sigma</math>, auch für das leere Wort. Dazwischen steht das feste Zeichen <math>E</math>.


===Schließende Klammer ohne Partner ablehnen===
Die kürzesten Wörter der Sprache sind <math>E</math> (mit <math>u = \varepsilon</math> und <math>v = \varepsilon</math>), <math>KE</math>, <math>EK</math> und <math>EE</math>. Von den acht Wörtern der Länge 3 gehören alle außer <math>KKK</math> dazu. Das leere Wort gehört nicht dazu, denn es enthält kein <math>E</math>.
Im Wort <math>())</math> gehört zur letzten schließenden Klammer keine öffnende.


{| class="wikitable" style="text-align:center"
Die Sprache ist unendlich: Hängt man an ein Wort aus <math>L_E</math> ein weiteres Zeichen an, entsteht ein längeres Wort, das ebenfalls ein <math>E</math> enthält. Eine Aufzählung aller Wörter ist deshalb nicht möglich. Der passende Automat steht im Beispiel [[Deterministischer endlicher Automat#Akzeptierte Sprache eines DEA beschreiben|Akzeptierte Sprache eines DEA beschreiben]].
! Schritt !! Zustand !! Resteingabe !! Keller (oben rechts)
|-
| 0 || <math>q_0</math> || <math>())</math> || <math>\#</math>
|-
| 1 || <math>q_1</math> || <math>))</math> || <math>\#K</math>
|-
| 2 || <math>q_1</math> || <math>)</math> || <math>\#</math>
|-
| 3 || <math>q_0</math> || <math>)</math> || <math>\#</math>
|}


Nach dem Klammerpaar wechselt der Automat mit dem <math>\varepsilon</math>-Übergang nach <math>q_0</math>. Dort trifft die übrige schließende Klammer auf das Kellerbodensymbol <math>\#</math>. Für diese Lage gibt es keinen Übergang, der Automat bricht ab. Die Eingabe ist nicht vollständig gelesen, das Wort wird abgelehnt.
===Sprache mit Wortpotenzen angeben===
Mit [[Wort#Wortpotenz|Wortpotenzen]] lassen sich unendliche Sprachen über <math>\Sigma = \{K; E\}</math> kurz angeben. Hinter dem Strich steht, welche Werte der Exponent <math>n</math> annehmen darf.


===Zwei Klammerarten mit zwei Kellerzeichen prüfen===
* '''<math>L_X = \{K^n E \mid n \ge 1\}</math>:''' Für <math>n = 1</math>, <math>n = 2</math> und <math>n = 3</math> entstehen die Wörter <math>KE</math>, <math>KKE</math> und <math>KKKE</math>. Die Sprache enthält alle Wörter aus mindestens einem <math>K</math> und einem abschließenden <math>E</math>. Das Wort <math>E</math> gehört nicht dazu, denn <math>n = 0</math> ist nicht erlaubt.
[[Datei:Kellerbelegung zwei Klammerarten.png|mini|Kellerbelegung beim Lesen von ([])]]
* '''<math>L_Y = \{(KE)^n \mid n \ge 0\}</math>:''' Hier wird das ganze Wort <math>KE</math> wiederholt. Für <math>n = 0</math>, <math>n = 1</math> und <math>n = 2</math> entstehen <math>\varepsilon</math>, <math>KE</math> und <math>KEKE</math>. Weil <math>n = 0</math> erlaubt ist, gehört das leere Wort zur Sprache.
In Programmen kommen runde und eckige Klammern gemischt vor. Jede schließende Klammer muss zur zuletzt geöffneten Klammer passen: <math>([])</math> ist korrekt, <math>(]</math> nicht. Neben dem Kellerbodensymbol reicht ein einziges Kellerzeichen dafür nicht mehr, denn der Automat muss sich die Art jeder offenen Klammer merken. Das Kelleralphabet ist <math>\Gamma = \{\#; R; E\}</math>: <math>R</math> steht für eine offene runde, <math>E</math> für eine offene eckige Klammer. Der Automat hat wie im ersten Beispiel die Zustandsmenge <math>Q = \{q_0; q_1\}</math>, den Startzustand <math>q_0</math> und die Endzustandsmenge <math>F = \{q_0\}</math>. Sein Eingabealphabet ist <math>\Sigma = \{(; ); [; ]\}</math>.
* '''Vereinigung und Schnitt:''' <math>L_X \cup L_Y</math> enthält alle Wörter, die zu mindestens einer der beiden Sprachen gehören, zum Beispiel <math>\varepsilon</math>, <math>KE</math>, <math>KKE</math> und <math>KEKE</math>. Das Wort <math>KE</math> gehört zu beiden Sprachen, es entsteht jeweils für <math>n = 1</math>. Es ist das einzige gemeinsame Wort: <math>L_X \cap L_Y = \{KE\}</math>.


{| class="wikitable" style="text-align:center"
Die Schreibweise legt für jedes Wort fest, ob es dazugehört. <math>KEK</math> gehört zu keiner der beiden Sprachen: Das Wort endet nicht mit <math>E</math> und ist deshalb weder von der Form <math>K^n E</math> noch eine Wiederholung von <math>KE</math>.
! Zustand !! Eingabe !! oben im Keller !! Folgezustand !! ersetzt durch
|-
| <math>q_0</math> || <math>(</math> || <math>\#</math> || <math>q_1</math> || <math>\#R</math>
|-
| <math>q_0</math> || <math>[</math> || <math>\#</math> || <math>q_1</math> || <math>\#E</math>
|-
| <math>q_1</math> || <math>(</math> || <math>R</math> || <math>q_1</math> || <math>RR</math>
|-
| <math>q_1</math> || <math>(</math> || <math>E</math> || <math>q_1</math> || <math>ER</math>
|-
| <math>q_1</math> || <math>[</math> || <math>R</math> || <math>q_1</math> || <math>RE</math>
|-
| <math>q_1</math> || <math>[</math> || <math>E</math> || <math>q_1</math> || <math>EE</math>
|-
| <math>q_1</math> || <math>)</math> || <math>R</math> || <math>q_1</math> || <math>\varepsilon</math>
|-
| <math>q_1</math> || <math>]</math> || <math>E</math> || <math>q_1</math> || <math>\varepsilon</math>
|-
| <math>q_1</math> || <math>\varepsilon</math> || <math>\#</math> || <math>q_0</math> || <math>\#</math>
|}


Eine schließende runde Klammer darf nur gelesen werden, wenn <math>R</math> oben liegt, eine schließende eckige nur, wenn <math>E</math> oben liegt. Das Protokoll für <math>([])</math>:
===Leere Sprache und Sprache mit dem leeren Wort unterscheiden===
Über <math>\Sigma = \{K; E\}</math> werden drei Sprachen verglichen:


{| class="wikitable" style="text-align:center"
{| class="wikitable" style="text-align:center"
! Schritt !! Zustand !! Resteingabe !! Keller (oben rechts)
! Sprache !! Anzahl der Wörter !! Gehört <math>\varepsilon</math> dazu? !! Gehört <math>K</math> dazu?
|-
| 0 || <math>q_0</math> || <math>([])</math> || <math>\#</math>
|-
| 1 || <math>q_1</math> || <math>[])</math> || <math>\#R</math>
|-
| 2 || <math>q_1</math> || <math>])</math> || <math>\#RE</math>
|-
|-
| 3 || <math>q_1</math> || <math>)</math> || <math>\#R</math>
| <math>\emptyset</math> || 0 || nein || nein
|-
|-
| 4 || <math>q_1</math> || <math>\varepsilon</math> || <math>\#</math>
| <math>\{\varepsilon\}</math> || 1 || ja || nein
|-
|-
| 5 || <math>q_0</math> || <math>\varepsilon</math> || <math>\#</math>
| <math>\{\varepsilon; K\}</math> || 2 || ja || ja
|}
|}


Alles ist gelesen, der Automat steht im Endzustand <math>q_0</math> und akzeptiert. Für <math>(]</math> ergibt sich:
Die leere Sprache <math>\emptyset</math> enthält gar kein Wort, auch nicht das leere. Die Sprache <math>\{\varepsilon\}</math> ist dagegen nicht leer: Sie enthält ein Wort, und dieses Wort hat die Länge 0.


{| class="wikitable" style="text-align:center"
Am Kaffeeautomaten bedeutet das: Die Sprache <math>\{\varepsilon\}</math> lässt genau eine Bestellfolge zu, nämlich die ohne jeden Tastendruck. Die Sprache <math>\emptyset</math> lässt keine Bestellfolge zu, auch diese nicht. Ein Automat ohne Endzustand akzeptiert kein Wort, seine Sprache ist <math>\emptyset</math>. Ein Automat, dessen Startzustand ein Endzustand ist, akzeptiert mindestens das leere Wort.
! Schritt !! Zustand !! Resteingabe !! Keller (oben rechts)
 
|-
===Sprachen vergleichen===
| 0 || <math>q_0</math> || <math>(]</math> || <math>\#</math>
Gegeben sind über <math>\Sigma = \{K; E\}</math> die Sprache <math>L_Z = \{w \in \Sigma^* \mid |w| = 2\}</math> aller Wörter aus zwei Zeichen und die Sprache <math>L_E</math> aller Wörter mit mindestens einem <math>E</math> aus dem Beispiel [[#Unendliche Sprache in Mengenschreibweise angeben|Unendliche Sprache in Mengenschreibweise angeben]].
|-
| 1 || <math>q_1</math> || <math>]</math> || <math>\#R</math>
|}


Oben liegt <math>R</math>, gelesen werden soll die schließende eckige Klammer. Für diese Lage gibt es keinen Übergang, der Automat bricht ab und lehnt das Wort ab.
# '''Aufzählen:''' <math>L_Z</math> ist endlich und enthält <math>2^2 = 4</math> Wörter: <math>L_Z = \{KK; KE; EK; EE\}</math>.
# '''Schnittmenge:''' Zu beiden Sprachen gehören die Wörter aus zwei Zeichen, die ein <math>E</math> enthalten: <math>L_Z \cap L_E = \{KE; EK; EE\}</math>.
# '''Teilmenge prüfen:''' <math>L_Z \subseteq L_E</math> gilt nicht, denn <math>KK \in L_Z</math>, aber <math>KK \notin L_E</math>. Auch <math>L_E \subseteq L_Z</math> gilt nicht, denn <math>E \in L_E</math>, aber <math>E \notin L_Z</math>. Jeweils ein Gegenbeispiel genügt.
# '''Vereinigungsmenge:''' <math>L_Z \cup L_E</math> enthält alle Wörter, die zwei Zeichen lang sind oder ein <math>E</math> enthalten. Dazu gehören zum Beispiel <math>KK</math>, <math>E</math> und <math>KKE</math>, nicht aber <math>K</math> oder <math>KKK</math>.


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