Inhaltsverzeichnis
Formale Sprachen und Automaten
Sie alle sprechen eine oder mehrere natürliche Sprachen, z.B. Deutsch, Englisch, Türkisch, Französisch usw. . Diese Sprachen ermöglichen es uns, untereinander Informationen auszutauschen, sie sind aber recht variantenreich, oft mehrdeutig und sehr komplex, sodass sie sich nur eingeschränkt zur Kommunikation mit Maschinen oder zur Kommunikation von Maschine zu Maschine eignen. Wir beschäftigen uns in diesem Kapitel daher mit einfacheren Sprachen, die sich exakt definieren lassen.
Beispiel: Wetter
Das aktuelle Wetter an einem vorgegebenen Ort kann durch Wörter der folgenden Form beschrieben werden:
| Wort | Bedeutung (Semantik) |
|---|---|
| 12°C ☼ | 12 Grad Celsius, sonnig |
| -10°C ☁ | -10 Grad Celsius, bewölkt |
| 8°C 🌧 | 8 Grad Celsius, regnerisch |
Definition: Alphabet, Wort, Syntax
Die endliche Menge aller Zeichen, die in einer formalen Sprache verwendet werden, heißt Alphabet oder Zeichenvorrat. Eine endliche Aneinanderreihung mehrerer Zeichen heißt Wort oder Zeichenkette.
Auch eine leere Zeichenkette ist ein Wort. Man bezeichnet sie mit dem Symbol $\varepsilon$.
Die Menge aller Wörter, die sich mit einem Alphabet $A$ bilden lassen, bezeichnet man mit dem Symbol $A*$.
Im Beispiel oben ist das Alphabet die Menge $A=$ {-, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, °, C, ☼, ☁, 🌧, }. Auch das Leerzeichen (letztes Element der Menge) gehört in diesem Beispiel zum Alphabet.
Die Menge aller Wörter, die sich mit dem Alphabet A bilden lassen, heißt Wortmenge $A^*$. In unserem Beispiel ist $A^*=\{\varepsilon,\ -,\ 0,\ 1,\ \ldots,\ -0,\ -1,\ldots \}$. Sie enthält unendlich viele Elemente.
Jede Teilmenge $L \subset A^*$ heißt formale Sprache über dem Alphabet A.
Die Regeln, die beschreiben, welche Wörter zur Sprache gehören, nennt man Syntax.
Die Syntax unserer "Wettersprache" könnte man beispielsweise so beschreiben:
"Zur Sprache gehören alle Wörter, die aus einer Temperatur gefolgt von einem Leerzeichen und wiederum gefolgt von einem der drei Wettersymbole bestehen."
Wir werden weiter unten deutlich bessere, exakte Möglichkeiten kennenlernen, die Syntax einer Sprache zu beschreiben.
Die Semantik eines Wortes ist seine Bedeutung. Es gibt oft Wörter einer Sprache, die syntaktisch korrekt sind, deren Semantik aber nicht sinnvoll ist, z.B. "-99°C 🌧"
Man sagt: Eine Sprache ist eine Teilmenge aller Wörter über einem Alphabet.
Beispiel-Wörter:
- "12°C ☼"
- "-10°C ☁" und
- "8°C 🌧"
sind der oben beschriebenen Syntax zufolge Wörter der oben beschriebenen Sprache.
- "☁☼3" oder
- "xz12"
sind keine Wörter der oben beschriebenen Sprache.
Und was ist dann ein Satz?
Der Begriff Wort einer Sprache umfasst in der Informatik auch Wörter, die Leerzeichen oder Zeilenumbrüche enthalten, also das, was in natürlichen Sprachen als Satz bezeichnet wird. Den Begriff Satz gibt es in der Informatik nicht. Ein syntaktisch korrektes Programm der Programmiersprache Java ist daher ein Wort dieser Sprache.
Aufgabe 1
Welches Alphabet hat die "Morse-Sprache"?
Aufgabe 2
Die Länge einer Zeichenkette $w$ bezeichnet man mit $|w|$.
Geben Sie die Menge aller Zeichenketten über dem Alphabet $A=\{0,\ 1\}$ an, die die maximale Länge 2 besitzen, d.h. $\{w\in A^*|\ |w| \le 2 \}$.