Dies ist eine alte Version des Dokuments!
Inhaltsverzeichnis
Formale Sprachen und Automaten
Sie alle sprechen eine oder mehrere naü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.
"12°C ☼", "-10°C ☁" und "8°C 🌧" sind der Syntax zufolge Wörter der oben beschriebenen Sprache. "☁☼3" oder "xz12" sind keine Wörter der oben beschriebenen Sprache.