2.2 Grundbegriffe Sprache
Sprachen bestehen aus einer Menge von Wörtern, welche wiederum aus Zeichen eines Alphabetes bestehen. Ein ganzes Gebiet der Informatik testet, ob ein gegebenes Wort zu einer Sprache gehört oder nicht. Beispielsweise übersetzen wir die Frage “Ist \(10.13.1997\) ein gültiges Datum?” zu der Frage “Ist \(10.13.1997\) ein Wort der Sprache, die Daten beschreibt?”.
Dazu definieren wir die aktuell noch unbekannten Begriffe. Starten wir mit der Definition eines Alphabets.
Definition: Alphabet
Ein Alphabet ist eine endliche, nichtleere Menge von Symbolen.
Als Notation für ein Alphabet wird häufig \(Σ\) verwendet.
Beispiele
- \(Σ = \{a, b, c, d, …, z\}\) ist die Menge der lateinischen Kleinbuchstaben.
- \(Σ = \{a, b, c\}\) ist die Menge der drei Symbole \(a\), \(b\) und \(c\).
- \(Σ = \{0, 1, 2, …, 9\}\) ist die Menge der arabischen Ziffern.
- \(Σ = \{0, 1\}\) ist das Boolsche Alphabet.
- \(Σ = \{01, 11\}\) ist ebenfalls ein Alphabet. Es besteht aus nur zwei Symbolen.
- \(Σ = \{+, -, ·, :\}\) ist die Menge für die Grundrechenarten.
- \(Σ_{Tast} \) ist die Menge aller Symbole der Rechnertastatur. Diese Menge ist nichtleer und endlich und bildet somit ein Alphabet.
- \(\mathbb{N}_0 = \{0, 1, 2, 3, ….\} \) ist eine unendliche Menge und somit kein Alphabet.
- \( \emptyset = \{ \} \) ist eine leere Menge und somit kein Alphabet.
Definition: Wort
Ein Wort ist eine endliche Folge von Symbolen eines bestimmten Alphabets.
Man sagt, ein Wort ist “über dem Alphabet \(Σ\) “.
Beispiele
- \(hallo\) ist ein Wort über dem Alphabet \(Σ = \{a, b, c, d, …, z\}\)
- \(abc \) und \(aac \) sind Wörter über dem Alphabet \(Σ = \{a, b, c\}\)
- \(2022\) ist ein Wort über dem Alphabet \(Σ = \{0, 1, 2, …, 9\}\)
- \( 01000, 1101, 0111, 011 \) und \(01\) sind Wörter über dem Alphabet \(Σ = \{0, 1\}\). Wörter über dem Boolschen Alphabet heissen Binärwörter.
- \( 012\) ist kein Wort über dem Alphabet \(Σ = \{0, 1\}\) aber es ist ein Wort über dem Alphabet \(Σ = \{0, 1, 2\}\).
- \(1101\) und \(0111\) sind Wörter über dem Alphabet \(Σ = \{01, 11\}\). Aber \(011\) ist kein Wort über dem Alphabet \(Σ = \{01, 11\}\).
- \( 1+2\) ist kein Wort über dem Alphabet \(Σ = \{+, -, ·, :\}\) aber \( ++:-\) ist ein Wort über dem Alphabet \(Σ = \{+, -, ·, :\}\).
- \(“Das \: ist \: ein \: \# ganzer \:*Satz \:mit @ \:Sonderzeichen.”\) ist ein Wort über dem Alphabet \(Σ_{Tast}\). Da \(Σ_{Tast}\) auch Leerschläge und Zeilenumbrüche beinhaltet, können wir ganze Abschnitte und Texte als Wörter über \(Σ_{Tast}\) bezeichnen.
Definition: leeres Wort
Das leere Wort ist ein Wort, das keine Symbole enthält. Es wird durch das Symbol \(ε\) dargestellt und ist ein Wort über jedem Alphabet.
Wortmengen und Sprachen
Eine formale Sprache ist nichts anderes als eine beliebige Teilmenge der Menge aller Wörter über einem gegebenen Alphabet.
Definition: Menge aller Wörter (Kleensche Hülle)
Die Menge aller Wörter (Kleenesche Hülle) über einem Alphabet \(Σ\) wird mit \(Σ^∗\) bezeichnet. \(Σ^*\) ist die Menge, die durch beliebiges Aneinanderhängen der Zeichen des Alphabetes bzw. der Wörter der Sprache entsteht. Da das Aneinanderhängen beliebig erfolgen kann, ist die kleenesche Hülle unendlich gross. \(Σ^+ = Σ^* \backslash \{ε\} (= Σ^* \) ohne leeres Wort\()\) ist die Menge aller nichtleeren Zeichenreihen über einem Alphabet \(Σ\).
Beispiel
Für das Boolsche Alphabet \(Σ = \{0, 1\}\) ist \(Σ^* = \{0, 1\}^* = \{ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, …\}\).
Definition: Sprache
Eine Teilmenge \(L \subset Σ^∗\) von Wörtern über einem Alphabet \(Σ\) wird als Sprache über \(Σ\) bezeichnet.
Merkhilfe: \(L\) steht für “language”.
Beispiele
- Deutsch ist eine Sprache über dem Alphabet der lateinischen Buchstaben, Umlaute, Leerzeichen, Satzzeichen etc. , wobei die Wörter einen grammatikalisch korrekten deutschen Text darstellen sollen.
- Programmiersprachen (wie Python) sind Sprachen über dem Alphabet des ASCII-Zeichensatzes, wobei die Programme eine korrekte Syntax aufweisen sollten.
- \(\{ε, 10, 01, 1100, 1010, 1001, 0110, 0011, . . .\}\) ist die Sprache der Wörter über \({0, 1}\) mit der gleichen Anzahl von Nullen und Einsen.
- \(Σ^*\) ist die Sprache über \(Σ\). Dies gilt für jedes Alphabet \(Σ\).
- \(\{ε\}\) ist die Sprache, die aus dem leeren Wort \(ε\) besteht. Diese Sprache ist wenig sinnvoll aber sie existiert für jedes Alphabet \(Σ\).
- \(\{\} = \emptyset\) ist die leere Sprache und existiert ebenfalls für jedes Alphabet. Achtung: \(\{ε\} \neq \emptyset \), denn \(\{ε\}\)besteht aus einem Symbol, während \( \emptyset \) keine Symbole hat.
Bemerkungen
- Wenn \(Σ_1 \subset Σ_2 \) gilt (also \(Σ_2 \) alle Symbole von \(Σ_1 \) enthält) und \(L\) eine Sprache ist über \(Σ_1 \), so ist \(L\) auch eine Sprache ist über \(Σ_2 \).
- Alphabete müssen aus endlich vielen Symbolen bestehen und Wörter haben auch eine endliche Länge. Sprachen aber können aus unendlich vielen Wörtern bestehen.
Notationen von Sprachen
Da Sprachen letztlich Mengen von Wörtern sind, können zur Beschreibung von Sprachen alle Mengen-Notationen gewählt werden.
Beispiel
Folgende Notationen beschreiben alle dieselbe Sprache.
- Aufzählende Darstellung: \(L = \{ε, a, b, ab, aaa, aab, abb, bbb, aaaa, …\}\)
- Beschreibende Darstellung: \(L \) ist die Menge der Wörter über dem Alphabet \(\{a, b\} \), wobei alle \(a\) vor allen \(b\) stehen.
- Mathematisch beschreibende Darstellung: \(L = \{w | w\) besteht aus beliebig vielen \( a \) gefolgt von beliebig vielen \( b \}\)
- Sehr mathematisch beschreibende Darstellung: \(L = \{a^mb^n| m,n \in \mathbb{N}_0\}\) (Die Notation \(a^m, b^n\) wird im nächsten Abschnitt erklärt.)
Hier haben Sie die Option Ihre Notizen zu diesem Abschnitt hochzuladen. Wir empfehlen eine sinnvolle Beschriftung z.B. 2_2_Grundbegriffe_FormaleSprache_Notizen.