Formale Sprache
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 (die Semantik) 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{ \{\varepsilon\} }[/math] enthält genau ein Wort, nämlich das leere Wort [math]\displaystyle{ \varepsilon }[/math].
- Die leere Sprache [math]\displaystyle{ \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 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]\displaystyle{ 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]\displaystyle{ w }[/math] auch ein Wortmuster stehen, das den Aufbau der Wörter zeigt, zum Beispiel mit einer Wortpotenz oder mit einem Platzhalter für ein beliebiges Wort. Hinter dem Strich steht dann, welche Werte die Variablen annehmen dürfen.
- 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.
Sprachen als Mengen
Weil formale Sprachen Mengen von Wörtern sind, gelten für sie alle Begriffe der Mengenlehre:
- 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.
- Teilmenge: [math]\displaystyle{ L_1 \subseteq L_2 }[/math] gilt, wenn jedes Wort aus [math]\displaystyle{ L_1 }[/math] auch zu [math]\displaystyle{ L_2 }[/math] gehört. Um zu zeigen, dass diese Beziehung nicht gilt, genügt ein einziges Wort aus [math]\displaystyle{ L_1 }[/math], das nicht in [math]\displaystyle{ L_2 }[/math] liegt (ein Gegenbeispiel).
- Schnitt und Vereinigung: Die Schnittmenge [math]\displaystyle{ L_1 \cap L_2 }[/math] enthält die Wörter, die zu beiden Sprachen gehören. Die Vereinigungsmenge [math]\displaystyle{ L_1 \cup L_2 }[/math] enthält die Wörter, die zu mindestens einer der beiden Sprachen gehören.
Beispiele
Sprache als Menge angeben
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_F }[/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].
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]\displaystyle{ L }[/math] des Kaffeeautomaten über [math]\displaystyle{ \Sigma = \{K; E\} }[/math] zeigt das der Vergleich zweier Eingaben:
- [math]\displaystyle{ KTE }[/math]: Das Zeichen [math]\displaystyle{ T }[/math] gehört nicht zum Alphabet ([math]\displaystyle{ T \notin \Sigma }[/math]). Die Zeichenfolge ist deshalb gar kein Wort über [math]\displaystyle{ \Sigma }[/math] ([math]\displaystyle{ KTE \notin \Sigma^* }[/math]) und kann zu keiner Sprache über [math]\displaystyle{ \Sigma }[/math] gehören.
- [math]\displaystyle{ KK }[/math]: Alle Zeichen stammen aus dem Alphabet, es gilt [math]\displaystyle{ KK \in \Sigma^* }[/math]. Das Wort erfüllt aber die Regel der Sprache nicht, weil es nur 2 Einheiten liefert. Deshalb gilt [math]\displaystyle{ KK \notin L }[/math].
Zuerst wird also geprüft, ob alle Zeichen zum Alphabet gehören, danach, ob das Wort die Regel der Sprache erfüllt.
Unendliche Sprache in Mengenschreibweise angeben
Gesucht ist die Sprache [math]\displaystyle{ L_E }[/math] aller Bestellfolgen über [math]\displaystyle{ \Sigma = \{K; E\} }[/math], die mindestens einen Espresso enthalten.
- Mit einer Bedingung: [math]\displaystyle{ L_E = \{w \in \Sigma^* \mid w \text{ enthält mindestens ein } E\} }[/math]
- Mit einem Wortmuster: [math]\displaystyle{ L_E = \{uEv \mid u \in \Sigma^* \text{ und } v \in \Sigma^*\} }[/math]. Die Platzhalter [math]\displaystyle{ u }[/math] und [math]\displaystyle{ v }[/math] stehen für beliebige Wörter über [math]\displaystyle{ \Sigma }[/math], auch für das leere Wort. Dazwischen steht das feste Zeichen [math]\displaystyle{ E }[/math].
Die kürzesten Wörter der Sprache sind [math]\displaystyle{ E }[/math] (mit [math]\displaystyle{ u = \varepsilon }[/math] und [math]\displaystyle{ v = \varepsilon }[/math]), [math]\displaystyle{ KE }[/math], [math]\displaystyle{ EK }[/math] und [math]\displaystyle{ EE }[/math]. Von den acht Wörtern der Länge 3 gehören alle außer [math]\displaystyle{ KKK }[/math] dazu. Das leere Wort gehört nicht dazu, denn es enthält kein [math]\displaystyle{ E }[/math].
Die Sprache ist unendlich: Hängt man an ein Wort aus [math]\displaystyle{ L_E }[/math] ein weiteres Zeichen an, entsteht ein längeres Wort, das ebenfalls ein [math]\displaystyle{ E }[/math] enthält. Eine Aufzählung aller Wörter ist deshalb nicht möglich. Der passende Automat steht im Beispiel Akzeptierte Sprache eines DEA beschreiben.
Sprache mit Wortpotenzen angeben
Mit Wortpotenzen lassen sich unendliche Sprachen über [math]\displaystyle{ \Sigma = \{K; E\} }[/math] kurz angeben. Hinter dem Strich steht, welche Werte der Exponent [math]\displaystyle{ n }[/math] annehmen darf.
- [math]\displaystyle{ L_X = \{K^n E \mid n \ge 1\} }[/math]: Für [math]\displaystyle{ n = 1 }[/math], [math]\displaystyle{ n = 2 }[/math] und [math]\displaystyle{ n = 3 }[/math] entstehen die Wörter [math]\displaystyle{ KE }[/math], [math]\displaystyle{ KKE }[/math] und [math]\displaystyle{ KKKE }[/math]. Die Sprache enthält alle Wörter aus mindestens einem [math]\displaystyle{ K }[/math] und einem abschließenden [math]\displaystyle{ E }[/math]. Das Wort [math]\displaystyle{ E }[/math] gehört nicht dazu, denn [math]\displaystyle{ n = 0 }[/math] ist nicht erlaubt.
- [math]\displaystyle{ L_Y = \{(KE)^n \mid n \ge 0\} }[/math]: Hier wird das ganze Wort [math]\displaystyle{ KE }[/math] wiederholt. Für [math]\displaystyle{ n = 0 }[/math], [math]\displaystyle{ n = 1 }[/math] und [math]\displaystyle{ n = 2 }[/math] entstehen [math]\displaystyle{ \varepsilon }[/math], [math]\displaystyle{ KE }[/math] und [math]\displaystyle{ KEKE }[/math]. Weil [math]\displaystyle{ n = 0 }[/math] erlaubt ist, gehört das leere Wort zur Sprache.
- Vereinigung und Schnitt: [math]\displaystyle{ L_X \cup L_Y }[/math] enthält alle Wörter, die zu mindestens einer der beiden Sprachen gehören, zum Beispiel [math]\displaystyle{ \varepsilon }[/math], [math]\displaystyle{ KE }[/math], [math]\displaystyle{ KKE }[/math] und [math]\displaystyle{ KEKE }[/math]. Das Wort [math]\displaystyle{ KE }[/math] gehört zu beiden Sprachen, es entsteht jeweils für [math]\displaystyle{ n = 1 }[/math]. Es ist das einzige gemeinsame Wort: [math]\displaystyle{ L_X \cap L_Y = \{KE\} }[/math].
Die Schreibweise legt für jedes Wort fest, ob es dazugehört. [math]\displaystyle{ KEK }[/math] gehört zu keiner der beiden Sprachen: Das Wort endet nicht mit [math]\displaystyle{ E }[/math] und ist deshalb weder von der Form [math]\displaystyle{ K^n E }[/math] noch eine Wiederholung von [math]\displaystyle{ KE }[/math].
Leere Sprache und Sprache mit dem leeren Wort unterscheiden
Über [math]\displaystyle{ \Sigma = \{K; E\} }[/math] werden drei Sprachen verglichen:
| Sprache | Anzahl der Wörter | Gehört [math]\displaystyle{ \varepsilon }[/math] dazu? | Gehört [math]\displaystyle{ K }[/math] dazu? |
|---|---|---|---|
| [math]\displaystyle{ \emptyset }[/math] | 0 | nein | nein |
| [math]\displaystyle{ \{\varepsilon\} }[/math] | 1 | ja | nein |
| [math]\displaystyle{ \{\varepsilon; K\} }[/math] | 2 | ja | ja |
Die leere Sprache [math]\displaystyle{ \emptyset }[/math] enthält gar kein Wort, auch nicht das leere. Die Sprache [math]\displaystyle{ \{\varepsilon\} }[/math] ist dagegen nicht leer: Sie enthält ein Wort, und dieses Wort hat die Länge 0.
Am Kaffeeautomaten bedeutet das: Die Sprache [math]\displaystyle{ \{\varepsilon\} }[/math] lässt genau eine Bestellfolge zu, nämlich die ohne jeden Tastendruck. Die Sprache [math]\displaystyle{ \emptyset }[/math] lässt keine Bestellfolge zu, auch diese nicht. Ein Automat ohne Endzustand akzeptiert kein Wort, seine Sprache ist [math]\displaystyle{ \emptyset }[/math]. Ein Automat, dessen Startzustand ein Endzustand ist, akzeptiert mindestens das leere Wort.
Sprachen vergleichen
Gegeben sind über [math]\displaystyle{ \Sigma = \{K; E\} }[/math] die Sprache [math]\displaystyle{ L_Z = \{w \in \Sigma^* \mid |w| = 2\} }[/math] aller Wörter aus zwei Zeichen und die Sprache [math]\displaystyle{ L_E }[/math] aller Wörter mit mindestens einem [math]\displaystyle{ E }[/math] aus dem Beispiel Unendliche Sprache in Mengenschreibweise angeben.
- Aufzählen: [math]\displaystyle{ L_Z }[/math] ist endlich und enthält [math]\displaystyle{ 2^2 = 4 }[/math] Wörter: [math]\displaystyle{ L_Z = \{KK; KE; EK; EE\} }[/math].
- Schnittmenge: Zu beiden Sprachen gehören die Wörter aus zwei Zeichen, die ein [math]\displaystyle{ E }[/math] enthalten: [math]\displaystyle{ L_Z \cap L_E = \{KE; EK; EE\} }[/math].
- Teilmenge prüfen: [math]\displaystyle{ L_Z \subseteq L_E }[/math] gilt nicht, denn [math]\displaystyle{ KK \in L_Z }[/math], aber [math]\displaystyle{ KK \notin L_E }[/math]. Auch [math]\displaystyle{ L_E \subseteq L_Z }[/math] gilt nicht, denn [math]\displaystyle{ E \in L_E }[/math], aber [math]\displaystyle{ E \notin L_Z }[/math]. Jeweils ein Gegenbeispiel genügt.
- Vereinigungsmenge: [math]\displaystyle{ L_Z \cup L_E }[/math] enthält alle Wörter, die zwei Zeichen lang sind oder ein [math]\displaystyle{ E }[/math] enthalten. Dazu gehören zum Beispiel [math]\displaystyle{ KK }[/math], [math]\displaystyle{ E }[/math] und [math]\displaystyle{ KKE }[/math], nicht aber [math]\displaystyle{ K }[/math] oder [math]\displaystyle{ KKK }[/math].