Mich hat noch nie jemand gefragt: Herr Rau, was lernt man eigentlich im Informatik-Studium? Deshalb hier eine Antwort.
In der Informatik geht es um Information und deren automatische Verarbeitung. Ein Teilbereich heißt theoretische Informatik, und den mochte ich im Studium recht gerne. Jedenfalls viel lieber als technischere Informatik, Signalübertragung und dergleichen.
In der theoretischen Informatik geht es unter anderem um Sprachen. Die sind dort allerdings als formale Sprachen sehr genau definiert. Denn das macht es leichter, Behauptungen über diese Sprachen aufzustellen und diese beweisen zu können. In diesem und einigen folgenden Blogeinträgen will ich das ein wenig erklären – auch deshalb, um mir selber die Details wieder in Erinnerung zu rufen.
Grundbegriffe: Alphabet, Wort, Sprache, Grammatik
Alphabet:
Eine endliche Menge von Zeichen, zum Beispiel:
- {a, b, c, d … z}
- oder auch nur {a, b}
- oder {Hund, Katze, Maus, der, die, das, frisst, jagt, mag}
- oder {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Wort:
Diese Zeichen lassen sich beliebig aneinanderreihen, zum Beispiel so:
- abccddzeffgg
- abbbabba
- derHundfrisstfrisstKatzedie
- 999022332
Statt Aneinanderreihung sagt man einfach Wort. Verwirrend ist vielleicht, dass das, was in einer natürlichen Sprache ein Satz ist, hier Wort heißt.
Sprache:
Jede Teilmenge aus der Menge aller möglichen Wörter zu einem Alphabet. Zum Beispiel, angelehnt an die oben genannten Alphabete:
- Die Menge aller Wörter (Aneinanderreihungen), die mit a beginnen.
aaabc ist ein Wort der Sprache, baaac nicht - Die Menge aller Wörter, die genau sechs Zeichen lang sind.
aaabbb ist ein Wort der Sprache, aaabb nicht - Die Menge aller Wörter, die einen sinnvollen deutschen Satz ergeben (wobei man noch genauer definieren muss, was sinnvoll heißt).
derHundmagdieKatze ist ein Wort der Sprache, derHundHundKatze nicht - Die Menge aller Wörter, die eine Primzahl darstellen.
23 ist ein Wort der Sprache, 24 nicht
Grammatik:
Wenn man eine Sprache, die aus endlich vielen Wörtern besteht, beschreiben möchte, kann man natürlich einfach alle die Wörter in einer langen Liste aufzählen. Das ist aber unübersichtlich. Und wenn die Wörter einer Sprache beliebig lang sein können (heißt in natürlicher Sprache: wenn die Sätze beliebig lang sein können), dann ist das sogar ganz unmöglich. Also gibt es endliche Grammatiken, die mit Hilfe von Ableitungsregeln die Sprache so beschreiben, dass mit Hilfe dieser Grammatik alle Wörter der Sprache erzeugt werden können.
Ein ganz simples Beispiel, angelehnt an natürliche Sprache:
Satz => Subjekt + Prädikat + Ergänzung
Subjekt => "Sie" oder "Er"
Prädikat => "lacht" oder "springt"
Prädikat => Prädikat + "und" + Prädikat
Ergänzung => "oft" oder "nie"Man fängt bei Satz an und ersetzt immer das links vom Pfeil durch das, was rechts vom Pfeil steht. Und das macht man immer so weiter, bis rechts nur noch Sachen in Anführungszeichen stehen. Mit diesen Regeln kann man dann die Sätze „Sie lacht oft“, „Sie lacht und springt nie“ oder „Er lacht und lacht und lacht oft“ erzeugen. Und unendlich viele mehr, wenn auch alle sehr langweilig sind.
Diese Grammatiken heißen auch Phrasenstrukturgrammatiken. Davon gibt es verschiedene Arten.
Die Chomsky-Hierarchie
Sie ist nach Noam Chomsky (vor ein paar Wochen 90 80 geworden) benannt. Bei Chomsky treffen sich Sprachwissenschaft und Informatik. Und es wird kompliziert. Deshalb gebe ich hier einen wohl erst einmal unverständlichen Überblick und werde in folgenden Blogebeiträgen auf die einzelnen Sprachen der Hierarchie nach und nach eingehen.
- Chomsky 0: Alle Sprachen, die sich überhaupt durch eine Grammatik beschreiben lassen.
- Chomsky 1: Eine Teilmenge davon, nämlich die Sprachen, die sich durch eine kontextsensitive Grammatik beschreiben lassen.
- Chomsky 2: Eine Teilmenge wiederum davon, nämlich die Sprachen, die sich durch eine kontextfreie Grammatik beschreiben lassen.
- Chomsky 3: Eine Teilmenge wiederum davon, nämlich die Sprachen, die sich durch eine reguläre Grammatik beschreiben lassen.
Die Fragen, die sich stellen, sind: Was bedeuten all diese Wörter? Worin unterscheiden sich die verschiedenen Sprachen? Zu welcher Art gehören Programmiersprachen und menschliche Sprachen, wenn man das überhaupt sagen kann? (Und vielleicht noch: Gibt es Sprachen, die sich gar nicht durch eine Grammatik beschreiben lassen? Ja, gibt es.)
Zu jeder dieser Sprachen, zu jeder Grammatik kann man einen Automaten konstruieren, der – im besten Fall – für beliebige Wörter entscheidet, ob das Wort zu einer bestimmten Sprache gehört oder nicht. Für Chomsky 1-3 gibt es solche Automaten. Für Chomsky 0 ist es ein bisschen schwieriger.
Sprachen vom Typ Chomsky 0 heißen auch rekursiv aufzählbar oder semi-entscheidbar. Das heißt, alle dazu gehörenden Wörter können von einem Automaten (und zwar einer Turingmaschine) aufgezählt beziehungsweise bestätigt werden. Wenn ein Wort allerdings nicht zur Sprache gehört, dann sagt die Maschine nichts darüber. Man weiß also nicht, ob die Maschine noch rechnet oder für immer rechnen wird. Man kann zwar die (unendlich vielen) Wörter der Sprache aufzählen, aber nicht die (unendlich vielen) Wörter, die nicht dazu gehören. Anders gesagt, es gibt keine Grammatik für die Sprache derjenigen Wörter, die nicht zu einer gegeben 0-Sprache gehören.
Hier noch einmal im Überblick. In den nächsten Einträgen will ich jeden Sprachtyp etwas genauer erklären. Wenn man mit den einfachen Sprachen anfängt, geht das auch ganz harmlos.
| Chomsky-Hierarchie | Sprachtyp | Grammatikart | Akzeptierende Maschine |
|---|---|---|---|
| Chomsky 0 | semi-entscheidbare/ rekursiv aufzählbare Sprachen | allgemeine Grammatik oder Phrasenstruktur-Grammatik | Turingmaschine |
| Chomsky 1 | kontextsensitive Sprache | kontextsensitive Grammatik | (nichtdeterministische) linear beschränkte Turingmaschine |
| Chomsky 2 | kontextfreie Sprache | kontextfreie Grammatik | Kellerautomat |
| Chomsky 3 | reguläre Sprachen | reguläre Grammatik (siehe auch reguläre Ausdrücke) | endliche Automaten |
Schreibe einen Kommentar