Mit Google fortfahren
Wenn du ein Passwort eingibst, entscheidet der Computer sofort: erlaubt oder nicht erlaubt. Auch eine Programmiersprache ist streng: Ein fehlendes Zeichen kann reichen, damit ein Programm nicht mehr passt. Genau dafür braucht die Informatik Sprachen, bei denen die Regeln eindeutig sind.
- Du verstehst, was eine formale Sprache ist.
- Du unterscheidest Menge, Alphabet, Symbol, Wort und Sprache.
- Du erkennst, warum nicht jede Zeichenfolge gültig ist.
- Du kannst einfache Beispiele prüfen und erklären.
Vom Alltag zur formalen Sprache
Im Alltag ist Sprache oft flexibel. Wenn jemand „Gib mal Heft“ sagt, verstehst du wahrscheinlich trotzdem, was gemeint ist. Ein Computer kann so nicht arbeiten. Er braucht klare Regeln.
Eine Menge ist eine Sammlung von Dingen. Die Reihenfolge ist dabei egal. Eine formale Sprache ist in der Informatik eine genau festgelegte Menge von Wörtern. Diese Wörter bestehen aus erlaubten Zeichen und müssen zu den Regeln der Sprache passen. „Wort“ bedeutet hier nicht unbedingt ein deutsches Wort. Es kann auch 1011, aabb oder ein ganzes Programm sein.
Eine Menge ist eine Sammlung von Elementen.
Eine formale Sprache ist eine Menge von gültigen Wörtern über einem festgelegten Zeichenvorrat.
Stell dir eine kleine Sprache für Ampelfarben vor.
Erlaubte Wörter sind: rot, gelb, gruen
Dann gehört rot zur Sprache. blau gehört nicht dazu, weil es nicht in der festgelegten Menge steht.
Formal heißt: Die Regeln sind so genau, dass man eindeutig entscheiden kann, ob etwas dazugehört oder nicht.
Interaktive Quizfrage wird geladen ...
Alphabet, Symbol und Wort
Damit eine formale Sprache entstehen kann, brauchst du zuerst Bausteine. Ein Symbol ist ein einzelner erlaubter Baustein. Ein Alphabet ist die Menge aller Symbole, die du benutzen darfst.
Ein Wort ist eine endliche Folge von Symbolen aus diesem Alphabet. Endlich bedeutet: Das Wort hört nach einer bestimmten Anzahl von Symbolen auf.
Ein Symbol ist ein einzelner Baustein einer formalen Sprache.
Ein Alphabet ist die Menge der erlaubten Symbole.
Ein Wort ist eine endliche Aneinanderreihung von Symbolen aus einem Alphabet.
Das Alphabet sei \(\Sigma = \{0, 1\}\).
Dann sind 0, 1, 00, 101 und 1110 Wörter über diesem Alphabet.
102 ist kein Wort über diesem Alphabet, weil 2 nicht erlaubt ist.
Das Zeichen \(\Sigma\) liest man „Sigma“. In der theoretischen Informatik steht es häufig für ein Alphabet.
Interaktiver Lückentext wird geladen ...
Interaktive Quizfrage wird geladen ...
Welche Wörter gehören zur Sprache?
Aus einem Alphabet kannst du sehr viele Wörter bilden. Aber eine formale Sprache enthält meist nur einige davon. Sie ist also eine Auswahl aus allen möglichen Wörtern über dem Alphabet.
Die Menge aller Wörter über einem Alphabet nennt man Kleenesche Hülle. Man schreibt dafür \(\Sigma^*\) und liest es „Sigma Stern“. Sie enthält auch das leere Wort. Das leere Wort ist ein Wort mit Länge 0. Es wird oft mit \(\varepsilon\) geschrieben.
Die Kleenesche Hülle \(\Sigma^*\) ist die Menge aller endlichen Wörter, die man aus dem Alphabet \(\Sigma\) bilden kann.
Das leere Wort \(\varepsilon\) ist ein Wort ohne Symbol.
Sei \(\Sigma = \{a, b\}\).
Dann gehören zu \(\Sigma^*\) zum Beispiel:
\(\varepsilon\), a, b, aa, ab, ba, bb, aaa
Eine Sprache über diesem Alphabet könnte aber nur diese Wörter enthalten: \(L = \{a, ab, abb\}\)
Dann ist ab in der Sprache \(L`. `bb` ist zwar über dem Alphabet bildbar, gehört aber nicht zu \)L$.
Das Alphabet sagt, welche Zeichen erlaubt sind. Die Sprache sagt, welche Wörter wirklich dazugehören.
Interaktive Quizfrage wird geladen ...
Syntax und Semantik
Bei formalen Sprachen prüft man zuerst den Aufbau. Der Aufbau nach Regeln heißt Syntax. Die Bedeutung eines Wortes heißt Semantik.
Ein Wort kann syntaktisch richtig sein, obwohl seine Bedeutung noch nicht betrachtet wird. In Programmiersprachen ist das wichtig: Erst muss der Code richtig gebaut sein. Danach kann man fragen, was er ausführt.
Die Syntax beschreibt, wie gültige Wörter oder Ausdrücke aufgebaut sein müssen.
Die Semantik beschreibt, welche Bedeutung ein gültiger Ausdruck hat.
In einer Mini-Sprache für Rechnungen seien Ausdrücke wie Zahl + Zahl erlaubt.
3 + 4 ist syntaktisch passend.
3 + ist syntaktisch nicht passend, weil nach dem Plus noch eine Zahl fehlt.
Die Semantik von 3 + 4 ist: Es wird addiert, und das Ergebnis ist 7.
Bei formalen Sprachen wird oft zuerst nur die Syntax festgelegt. Die Semantik kann später zusätzlich definiert werden.
Interaktive Quizfrage wird geladen ...
Grammatiken erzeugen Sprachen
Eine formale Sprache kann man durch Aufzählen festlegen. Das geht gut bei kleinen endlichen Sprachen. Bei großen oder unendlichen Sprachen braucht man Regeln.
Eine Grammatik ist ein Regelwerk, mit dem Wörter einer Sprache erzeugt werden können. Dabei startet man oft mit einem Startzeichen und ersetzt Zeichen Schritt für Schritt nach festen Regeln.
Ein Nichtterminalsymbol ist ein Zeichen, das noch ersetzt werden muss. Ein Terminalsymbol ist ein fertiges Zeichen, das im Ergebnis stehen bleibt.
Eine Grammatik ist eine Menge von Regeln, mit denen gültige Wörter einer formalen Sprache gebildet werden.
Ein Startsymbol ist das Zeichen, bei dem eine Ableitung beginnt.
Eine Ableitung ist die schrittweise Anwendung von Regeln, bis ein fertiges Wort entsteht.
Ein Nichtterminalsymbol muss noch ersetzt werden.
Ein Terminalsymbol bleibt als fertiges Zeichen im Wort stehen.
Eine sehr kleine Grammatik soll Wörter aus gleich vielen a und b erzeugen, zuerst alle a, dann alle b.
Startsymbol: S
Regeln:
S -> ab
S -> aSb
Hier ist S ein Nichtterminalsymbol. Es wird noch ersetzt. a und b sind Terminalsymbole. Sie bleiben am Ende stehen.
Ableitungen:
S -> ab ergibt ab
S -> aSb -> aaSbb -> aaabbb
Im letzten Schritt wurde in aaSbb das S durch ab ersetzt. So entsteht aaabbb.
So entstehen Wörter wie ab, aabb, aaabbb.
Eine Grammatik ist wie eine Bauanleitung. Sie beschreibt nicht jedes Wort einzeln, sondern zeigt, wie gültige Wörter entstehen.
Interaktive Quizfrage wird geladen ...
Konkatenation
Wenn du zwei Wörter hintereinanderhängst, nennt man das Konkatenation. Das Wort ab konkateniert mit ba ergibt abba.
Auch Sprachen kann man verknüpfen. Wenn eine Sprache Wörter für Anfänge enthält und eine andere Sprache Wörter für Enden, entsteht durch Konkatenation eine neue Sprache mit allen passenden Kombinationen. Andere Mengenoperationen wie Vereinigung oder Schnitt gibt es auch. Hier reicht zuerst die Konkatenation, weil sie beim Bauen von Wörtern besonders wichtig ist.
Konkatenation bedeutet: Zeichen oder Wörter werden direkt hintereinandergefügt.
Sei \(L_1 = \{a, b\}\) und \(L_2 = \{00, 11\}\).
Dann enthält \(L_1L_2\) alle Wörter, die mit einem Wort aus \(L_1\) beginnen und mit einem Wort aus \(L_2\) enden:
\(L_1L_2 = \{a00, a11, b00, b11\}\)
Das leere Wort verändert beim Anhängen nichts.
abc mit \(\varepsilon\) ergibt wieder abc.
Das ist anders als die leere Menge. Eine leere Menge enthält kein Wort, mit dem man etwas verbinden könnte.
Interaktiver Lückentext wird geladen ...
Interaktive Quizfrage wird geladen ...
Zusammenfassung
Eine formale Sprache hilft dir, Zeichenfolgen eindeutig zu prüfen. Sie besteht aus Wörtern, die nach festen Regeln aus einem Alphabet gebildet werden. Nicht jede mögliche Zeichenfolge ist automatisch gültig.
Interaktive Lernkarten wird geladen ...
Interaktive Mindmap wird geladen ...
Interaktive Quizfrage wird geladen ...