Formale Sprache
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]\displaystyle{ L }[/math] über einem Alphabet [math]\displaystyle{ \Sigma }[/math] ist eine Teilmenge [math]\displaystyle{ L \subseteq \Sigma^* }[/math]. [math]\displaystyle{ \Sigma^* }[/math] ist die Menge aller Wörter über [math]\displaystyle{ \Sigma }[/math] einschließlich des leeren Wortes. Anders als bei natürlichen Sprachen entscheiden nur die Regeln, die Bedeutung spielt keine Rolle.
Für jedes Wort [math]\displaystyle{ w \in \Sigma^* }[/math] gilt entweder [math]\displaystyle{ w \in L }[/math] oder [math]\displaystyle{ w \notin L }[/math].
Alphabet und Wort
Zeichen und Alphabet
Ein Zeichen ist ein einzelnes Symbol, etwa ein Buchstabe, eine Ziffer oder ein Sonderzeichen. Ein Alphabet [math]\displaystyle{ \Sigma }[/math] ist eine endliche, nicht leere Menge von Zeichen. Seine Elemente heißen auch Buchstaben des Alphabets.
Wort und Wortlänge
Ein Wort über [math]\displaystyle{ \Sigma }[/math] ist eine endliche Folge von Zeichen aus [math]\displaystyle{ \Sigma }[/math]. Die Länge [math]\displaystyle{ |w| }[/math] eines Wortes [math]\displaystyle{ w }[/math] ist die Anzahl seiner Zeichen.
Die Verkettung zweier Wörter [math]\displaystyle{ u }[/math] und [math]\displaystyle{ v }[/math] hängt [math]\displaystyle{ v }[/math] an [math]\displaystyle{ u }[/math] an und ergibt das Wort [math]\displaystyle{ uv }[/math]. Dabei gilt [math]\displaystyle{ |uv| = |u| + |v| }[/math]. Die Reihenfolge ist wesentlich: [math]\displaystyle{ uv }[/math] und [math]\displaystyle{ vu }[/math] sind im Allgemeinen verschiedene Wörter.
Leeres Wort
Das leere Wort [math]\displaystyle{ \varepsilon }[/math] enthält kein Zeichen, es gilt [math]\displaystyle{ |\varepsilon| = 0 }[/math]. Es ist ein Wort über jedem Alphabet, gehört aber nicht zum Alphabet. Beim Verketten ändert es nichts: [math]\displaystyle{ w\varepsilon = \varepsilon w = w }[/math].
Zwei Sprachen werden leicht verwechselt: Die Sprache [math]\displaystyle{ \{\varepsilon\} }[/math] enthält ein Wort, nämlich das leere Wort. Die leere Sprache [math]\displaystyle{ \emptyset }[/math] enthält kein Wort.
Beschreibung formaler Sprachen
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.
- Mengenschreibweise: Eine Bedingung legt fest, welche Wörter zur Sprache gehören, in der Form [math]\displaystyle{ L = \{w \in \Sigma^* \mid \text{Bedingung}\} }[/math]. Das geht auch bei unendlichen Sprachen.
- Automat: Ein Automat [math]\displaystyle{ A }[/math] akzeptiert oder lehnt ein Wort ab. Die Menge aller akzeptierten Wörter ist die Sprache [math]\displaystyle{ L(A) }[/math].
- Grammatik: Eine Grammatik [math]\displaystyle{ G }[/math] erzeugt Wörter mit Regeln. Die Menge aller erzeugten Wörter ist die Sprache [math]\displaystyle{ 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.
Beispiele
Sprache als Menge angeben

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]\displaystyle{ \Sigma = \{K, E\} }[/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:
| Wort | Einheiten |
|---|---|
| KKKK | 1 + 1 + 1 + 1 = 4 |
| EE | 2 + 2 = 4 |
| EKK | 2 + 1 + 1 = 4 |
| KEK | 1 + 2 + 1 = 4 |
| KKE | 1 + 1 + 2 = 4 |
Die Sprache ist endlich, deshalb genügt die Aufzählung:
- [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 Automat im Bild akzeptiert genau die Wörter von [math]\displaystyle{ L }[/math]. Sein Aufbau steht im Beispiel Kaffeeautomat als vollständigen DEA angeben.
Wortzugehörigkeit prüfen
Ob ein Wort zur Sprache [math]\displaystyle{ L }[/math] aus dem vorigen Beispiel gehört, zeigt die Summe seiner Einheiten. Sie muss genau 4 betragen.
- [math]\displaystyle{ KEK \in L }[/math]: 1 + 2 + 1 = 4 Einheiten. Das Satzfach ist genau voll. Die Länge ist [math]\displaystyle{ |KEK| = 3 }[/math].
- [math]\displaystyle{ EEK \notin L }[/math]: 2 + 2 + 1 = 5 Einheiten. Das Satzfach läuft über.
- [math]\displaystyle{ KK \notin L }[/math]: 1 + 1 = 2 Einheiten. Das Satzfach ist nicht voll.
- [math]\displaystyle{ \varepsilon \notin L }[/math]: Das leere Wort hat 0 Einheiten, es gilt [math]\displaystyle{ |\varepsilon| = 0 }[/math]. Das Satzfach bleibt leer.