Monat: Februar 2009

1. Überblick und Wiederholung

Im Lauf dieser Serie habe ich formale Sprachen vorgestellt, dann eine Untergruppe davon, die regulären Sprachen. Im letzten Beitrag ging es dann um eine übergeordnete Gruppe, die kontextfreien Sprachen. Die ersteren haben praktische Anwendungen etwa bei den regulären Ausdrücken, die für Suchen/Ersetzen genutzt werden. Die zweite Gruppe ist wichtig beim Beschreiben von natürlichen Sprachen und vor allem von Programmiersprachen.

Die beiden übrigen Gruppen von Sprachen haben weniger direkte Anwendungsmöglichkeiten. Allerdings sind sie für die theoretische Informatik trotzdem interessant. Deshalb will ich jetzt etwas weiter ausholen und fange von der anderen Ecke an.

Zur Wiederholung:

1. Ein Alphabet ist eine endliche Menge von Zeichen, zum Beispiel {a,b} oder {a,b c, d, e, f, … z}. Diese Zeichen können alle aus mehr als einem Buchstaben bestehen, können auch das sein, was man konventionell unter Wörtern versteht. Wichtig ist nur, dass sie für die Zwecke der Sprachbeschreibung als unteilbar betrachtet werden. Das Alphabet einer Programmiersprache besteht also etwa aus {if, else, while, for …}, aber ich beschränke mich in den meisten meiner Beispiel auf das einfache Alphabet {a, b}.
2. Ein Wort ist eine beliebige endliche Folge von Zeichen aus einem Alphabet.
3. Eine Sprache ist eine Teilmenge aller möglichen Wörter, die man aus einem Alphabet bilden kann.

Die Wörter von endlichen Sprachen kann man einfach aufzählen, aber selbst das kann umständlich werden, und bei Sprachen, die aus unendlich vielen Wörtern bestehen, geht das schon mal gar nicht. Gibt es überhaupt Sprachen mit unendlich vielen Wörtern? Ja klar, wenn die Wörter beliebig lang sein können. Die Menge der Primzahlen ist unendlich groß, und die Menge aller Primzahl-Darstellungen in Dezimalschreibweise ebenso: {2, 3, 5, 7, 11, 13, 17, 19…}. Das Alphabet zu dieser Sprache besteht aus zehn Zeichen und sieht so aus: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Wenn man eine Sprache mit unendlich vielen Wörtern beschreiben will, kann man das mit einer Phrasenstruktur-Grammatik tun. Die umfangreichsten Bestandteile einer solchen Grammatik sind die Produktionsregeln, zum Beispiel:
A -> b
Diese Regel besagt, dass ich immer dann, wenn in einer Zeichenfolge ein “A” auftaucht, ich es durch ein “b” ersetzen kann.

Wieso die Unterscheidung zwischen Groß- und Kleinbuchstaben? Unser Alphabet sei weiterhin nur {a, b}. Wörter können also nur aus diesen Zeichen bestehen, alles, was andere Zeichen enthält, kann schon mal überhaupt nicht Teil der Sprache sein. Grammatiken benutzen allerdings zusätzlich so eine Art Hilfsvariablen. Die dürfen natürlich nicht so aussehen wie die Zeichen des Alphabets, und damit es da keine Verwechslung gibt, nimmt man konventionell Großbuchstaben für die Hilfsvariablen, in Zukunft “Nichtterminale” genannt, und Kleinbuchstaben für Alphabetzeichen oder “Terminale”. Das ist aber nur eine Konvention.

Mit einer Grammatik – also einem Alphabet, einer Menge an Nichtterminalen, einem Startpunkt und vor allem einer Menge an Produktionsregeln – kann man Wörter erzeugen. Nehmen eine Beispielgrammatik mit dem Alphabet {a, b}, den Nichtterminalen {S} und diesen Produktionsregeln (der Strich | steht als Abkürzung für “oder”):

1. S -> bS | aS | b

Damit kann ich verschiedene Wörter ableiten. Man beginnt immer beim Startpunkt S und ersetzt den Teil links vom Pfeil durch den Teil rechts vom Pfeil. Wenn etwas herauskommt, was nur noch aus Kleinbuchstaben besteht, dann ist die Ableitung dieses Wortes fertig:
S -> b
S -> bS -> bb
S -> bS -> bbS -> bbb
S -> aS -> aaS -> aaaS -> aaaab
S -> bS -> baS -> baaS -> baabS -> baabb
Diese Grammatik beschreibt die (unendlich umfangreiche) Sprache aller Wörter, die auf b enden.

2. Die vier wichtigsten Grammatik-Arten

2.1 Allgemeine Phrasenstrukturgrammatiken (Chomsky‑0)

Für alle Phrasenstrukturgrammatiken gilt: links vom Pfeil muss mindestens ein Nichtterminal stehen. Denn nur aus Nichtterminalen kann man ableiten. Regeln können also so aussehen:

aAa -> baAab
A -> BBBBB
A -> B
aAa -> B

Sprachen, die durch eine solche allgemeine Grammatiken beschrieben werden, gehören zum Typ Chomsky 0. Ihnen werde ich ich einen späteren Blogeintrag widmen. Vorgeschmack 1: Mit einer solchen Grammatik kann man die Wörter aller Sprachen aufzählen, die sich überhaupt irgendwie aufzählen lassen. Was man mit einer Chomsky-0-Grammatik nicht darstellen kann, kann man auch mit keinem anderen Mittel aufzählen. Vorgeschmack 2: Alles, was sich überhaupt berechnen lässt, lässt sich mit einer solchen Grammatik berechnen. Was sich mit einer Chomsky-0-Grammatik nicht berechnen lässt, kann man auch mit keinem anderen Mittel berechnen.
Was das Erzeugen von Wörtern mit Berechnen zu tun hat, werde ich weiter unten erklären.

2.2 Kontextsensitive bzw. monotone Grammatiken (Chomsky‑1)

Es gilt all das oben gesagte, nur mit der weiteren Einschränkung, dass die Produktionsegeln alle folgende Form haben müssen:
xAy -> xzy, wobei x und y beliebige Kombinationen sind und auch leer sein dürfen. A ist ein Nichtterminal, z eine beliebige, aber nicht leere Zeichenfolge.
Die Regeln sehen zum Beispiel so aus:

A -> a
A -> aB
bA -> baB

An den letzten beiden Regeln sieht man, warum diese Grammatik kontextsensitiv heißt. Die vorletzte Regel lautet, dass jedes A durch aB ersetzt werden kann, egal in welchem Zusammenhang es steht. Die letzte Regel sagt indirekt auch, dass ein A durch aB ersetzt werden kann, aber eben nur dann, wenn direkt davor ein b kommt. Der Kontext ist also wichtig.

Alternativ kann man einen anderen Aspekt dieser Sprachen betonen und die Einschränkung anders formulieren: Links vom Pfeil dürfen nie mehr Zeichen stehen als rechts vom Pfeil. Diese Art Grammatik heißt dann nicht kontextsensitiv, sondern “monoton”. Die Regeln können so aussehen:

A->a
aA->Bb
AAA->bbbbb
AA -> bb

Die Grammatik heißt deshalb monoton, weil die Ableitungen nie kürzer werden, sondern immer gleich viele Zeichen haben wie die Vorgänger oder noch mehr. Das ist das gleiche “monoton” wie in “monoton steigend” aus der Kurvendiskussion im Mathematikunterricht.

Man kann jede monotone in eine kontextsensitive Grammatik umwandeln. (Andersrum braucht man das nicht, da laut der Definition oben jede kontextsensitive Grammatik ohnehin monoton ist.) Beide Arten beschreiben die gleiche Art von Sprache, die kontextsensitiven Sprachen (Chomsky 1).

Zu den kontextsensitiven Sprachen gehört die Verdopplungssprache, also die Sprache aller Wörter mit der Eigenschaft, dass die erste Hälfte des Worts gleich der zweiten Hälfte ist. Man kann auch menschliche Sprachen und Programmiersprachen mit einer kontextsensitiven Grammatik beschreiben. Allerdings erfordert diese Grammatikart so viel Rechenzeit (siehe unten), dass man sich in der Praxis mit kontextfreien Grammatiken begnügt oder mit anderen, nur ein bisschen kontextsensitiven Grammatikwn, die in der Komplexität zwischen Chomsky 1 und Chomsky 2 liegen.

2.3 Kontextfreie Phrasenstrukturgrammatiken (Chomsky‑2)

Siehe älteren Beitrag.
Wie oben, mit der zusätzlichen Einschränkung, dass links vom Pfeil nur genau ein Zeichen stehen darf. Und das muss logischerweise dann immer ein Nichtterminal sein, da ja ganz allgemein gilt, dass es davon links immer mindestens eines geben muss. Typische Regel:

A -> aaBbb

Diese Regel heißt kontextfrei, weil jedes A durch aaBbb ersetzt werden kann, egal in welchem Kontext es steht. Zu den kontextfreien Sprachen gehören im großen und ganzen die Programmiersprachen. Oder die Sprache {aⁿbⁿ, wobei das ⁿ für die Anzahl hintereinander folgenden n gehört}.

2.4 Reguläre Grammatiken (Chomsky‑3)

Siehe älteren Beitrag.
Wie oben, nur mit der zusätzlichen Einschränkung, dass rechts vom Pfeil nur stehen darf: 1 Terminal oder 1 Nichtterminal oder 1 Terminal, gefolgt von 1 Nichterminal. (Oder andersrum, erst das NT, dann das T, aber dann immer so.) Typische Regeln:

A -> a | B | aB

3. Sprachen und Rechnen

Wieso überhaupt berechnen? Was haben Wörter mit Berechnungen zu tun? Viel. Nehmen wir als Alphabet diese Menge an Zeichen: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, .}, dann sind Wörter dazu zum Beispiel: 1, 10, 2.4, 101, 993, 256, 3.14159 und alle anderen denkbaren Kombinationen.
Sprachen zu diesem Alphabet könnten sein: {alle nichtnegativen geraden Zahlen} oder {alle Primzahlen} oder {alle Zahlen mit der Quersumme 7} oder {alle Zahlen n, für die gilt aⁿ+bⁿ=cⁿ}. Wenn man eine Grammatik hat, mit der man genau die Sprache erzeugen kann, die aus gesuchten Wörtern besteht, dann hat man eine Grammatik, mit der man diese Aufgaben berechnen kann.

Als Beispiel für eine Grammatik, die nur nichtnegative gerade Zahlen erzeugt, habe ich einfach die Beispielgrammatik von oben genommen (für die Sprache aller Wörter, die auf b enden) und nur wenig geändert:

1. S -> GS | US | G
2. G -> 0 | 2 | 4 | 6 | 8
3. U -> 1 | 3 | 5 | 7 | 9

Beispielableitung: S -> US -> UGS -> UGUS -> UGUG -> 1GUG -> 12UG > 123G -> 1232

Wenn man wissen will, ob eine Zahl eine gerade Zahl ist, muss man schauen, ob sie mit der Grammatik erzeugt werden kann => Wortproblem.

Die Aussagen “Man kann etwas berechnen” und “Es gibt eine Grammatik, die die entsprechenden Wörter (und nur die) erzeugt” sind äquivalent. Wie man das begründen kann, steht im nächsten Eintrag. Die Grammatik für {alle Zahlen n, für die gilt aⁿ+bⁿ=cⁿ, mit a,b,c,n als ganzen Zahlen} wäre zwar absurd kompliziert, und bis vor einem guten Jahrzehnt hätte man nicht gewusst, ob man das überhaupt berechnen kann, und wenn ja, wie. Aber da es sich berechnen lässt, wie man inzwischen weiß, ist prinzipiell auch eine Grammatik dazu möglich. Die dazu gehörende Sprache sieht übrigens so aus {2} {1, 2}, aber das weiß man halt auch erst hinterher.

Denkbarer ist eine Grammatik für die Sprache {alle Primzahlen}. Mit einer regulären Grammatik geht das nicht, mit einer kontextfreien auch nicht, mit einer kontextsensitiven – vermutlich schon, obwohl ich das Beispiel nirgendwo gefunden habe. Aber nach den nächsten Abschnitten wird vielleicht klar, wie ich zu der Annahme komme. Mit einer allgemeinen Grammatik, also vom Typ Chomsky 0, lässt sich diese Sprache auf jeden Fall beschreiben – denn bekanntlich lässt sich alles, was sich berechnen lässt, mit einer solchen Grammatik beschreiben. Und dass sich berechnen lässt, ob eine gegebene Zahl eine Primzahl ist oder nicht, das weiß man, da es Algorithmen dafür gibt (mit dem Sieb des Eratosthenes etwa).

4. Das Wortproblem

Für alle Sprachen ist das Wortproblem interessant: Gehört ein gegebenes Wort zur Sprache L oder nicht? Für reguläre und kontextfreie Sprachen ist das Wortproblem relativ leicht zu lösen. Es gibt Algorithmen dafür, man kritzelt ein bisschen mechanisch auf dem Papier herum oder lässt den Computer rechnen, und nach kurzer Zeit weiß man, ob das Wort zur Sprache gehört oder nicht. Kunststück: Beim Suchen nach einem regulären Ausdruck im Textverarbeitungsprogramm muss das Programm ja für jede Zeichenfolge überprüfen, ob sie zu der von dem regulären Ausdruck beschriebenen Sprache gehört oder nicht. Und beim Programmieren macht einen die Java-Programmierumgebung darauf aufmerksam, dass da irgendwo ein Fehler ist, dass zum Beispiel eine Klammer fehlt – dass das gegebene Programm eben nicht zur Sprache {alle syntaktisch korrekten Java-Programme} gehört.

Auch für kontextsensitive Sprachen ist das Wortproblem “entscheidbar”. Entscheidbar heißt, dass man sicher sagen kann, ob ein gegebenes Wort zu einer gegebenen kontextsensitiven Sprache gehört, oder ob das nicht der Fall ist.

Allerdings kann die Berechnung happig werden. Bei manchen Sprachen vom Typ Chomsky 1 wächst die erforderliche Rechenzeit nur polynomiell an, bei anderen dagegen zum Beispiel exponentiell. Vereinfacht gesagt, wenn man für ein Wort der Länge n berechnen will, ob es zur Sprache gehört, braucht man im ersten Fall größenordnungsmäßig n² Rechenschritte, was viel, aber machbar ist. Für andere Sprachen braucht man dagegen größenordnungsmäßig 2ⁿ Rechenschritte, was für lange Wörter äußerst viele Rechenschritte erfordert.
Gehen wir mal davon aus, das ein Rechenschritt eine Millionstelsekunde braucht. Braucht man für ein Wort der Länge 100 im ersten Fall 1/100 Sekunde, sind es im anderen Fall 4*10¹⁴ Jahre. Aber das mit dem P und dem NP ist eigentlich schon wieder ein anderes, auch sehr spannendes Thema.

Notfalls probiert man einfach alles aus, und zwar nach dem folgenden Algorithmus:

Schritt 1: Nimm den Startpunkt S und wende jede darauf anwendbare Regel an.
Schritt 2: Wende jede anwendbare Regel auf die in Schritt 1 enstandenen Zeichenfolgen an.
Schritt 3: Wende jede anwendbare Regel auf die in Schritt 2 enstandenen Zeichenfolgen an.
Und immer so weiter.

Hier die Produktionsregel für ein möglichst einfaches Beispiel:

1. S -> aSBC
2. S -> aBC
3. CB -> BC
4. aB -> ab
5. bB -> bb
6. bC -> bc
7. cC -> cc

Man beginnt bei S und wendet, wie oben angeben, nach und nach jede anwendbare Regel an. Und immer so weiter. Ich habe mal den Anfang des so entstehenden Baums aufgezeichnet. Die Ziffern geben jeweils die Nummer der Regel an, die angewendet wurde, um von der oberen Zeichenfolge zur darunter stehenden zu kommen.

Von manchen Zeichenfolgen aus geht keine weitere Verzweigung mehr ab. Das kann daran liegen, dass die Zeichenfolge nur noch aus Terminalen besteht (also ein Wort der Sprache ist, die von der Grammatik beschrieben wird) oder daran, dass man in eine Sackgasse geraten ist und sich keine der Regeln mehr anwenden lässt. Das ist Pech, aber das ist ein Problem bei kontextsensitiven Grammatiken, anders als bei den bisher behandelten Typen Chomsky 3 und Chomsky 2.

Um zu begründen, dass sich das Wortproblem entscheiden lässt, macht man sich die Eigenschaft zu nutze, dass die Grammatik monoton ist, also nie zu kürzeren Zeichenfolgen führt. Wenn ich wissen will, ob “aabc” zu der Sprache gehört, gehe ich einfach solange allen Zweigen nach, bis ich a) keine Regel mehr anwenden kann oder b) die Zeichenfolge im Zweig länger als 4, der Länge meines Ausgangsworts, geworden ist. Wenn das Wort bis dahin nicht konstruiert worden ist, dann wird es das auch nie werden – denn kürzer können die Zeichenfolgen nicht werden. Man sieht also aus dem Bäumchen oben, dass “aabc” genauso wenig ein Wort der Sprache ist wie “bca” oder “abbc”. Wenn ich wissen will, ob “aaabbbccc” (Länge 9) zur Sprache gehört, muss ich den Baum noch weiter aufspannen – bis alle Zweige zu Sackgassen oder länger als 9 werden oder ich vorher auf dieses Wort stoße.

Die Anzahl der Zweige wächst exponentiell mit der Länge des zu überprüfenden Wortes, das heißt, dass auch die Rechenenzeit exponentiell wächst, wie oben beschrieben. Aber früher oder später, notfalls viel später, hat man eine eindeutige Antwort, ob das Wort dazu gehört oder nicht.

5. Offene Fragen bis zum nächsten Mal

Wie wird begründet, dass man mit einer Chomsky-0-Grammatik alles berechnen kann, was man überhaupt berechnen kann?
Was kann man denn nicht berechnen?
Wie begründet man, dass etwas nicht berechenbar ist?