Dies ist eine alte Version des Dokuments!
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.
Im Beispiel oben ist das Alphabet die Menge {-, 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 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"?