Informatik 12/13 (G9)

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== Formale Sprachen und Automaten ======
<WRAP center round tip 80%>
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. \\ \\ 
</WRAP>

===== 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 =====
<WRAP center round info 80%>
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.
</WRAP>

<WRAP center round tip 80%>
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. \\ \\ 
</WRAP>

==== 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 \}$.