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
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.
"12°C ☼", "-10°C ☁" und "8°C 🌧" sind Wörter der oben beschriebenen Sprache. "☁☼3" oder "xz12" sind keine Wörter der oben beschriebenen Sprache.