Formale Sprachen, Teil 4: Kontextsensitive Sprachen (und Überblick)

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 {anbn, wobei das n 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 an+bn=cn}. 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 an+bn=cn, 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 n2 Rechenschritte, was viel, aber machbar ist. Für andere Sprachen braucht man dagegen größenordnungsmäßig 2n 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*1014 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.

chomsky1-baum

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?

Tagged: Tags

36 Thoughts to “Formale Sprachen, Teil 4: Kontextsensitive Sprachen (und Überblick)

  1. S -> bB -> bb
    Hier müsste doch aber mindestens ein a noch vorkommen, da ja nur gilt:
    B -> bB | aS, aber nicht B -> b
    Oder irre ich mich da (was um diese Uhrzeit ja durchaus mal vorkommen kann)?

  2. Ha, ein lange ersehnter Eintrag! Danke! :D

    „Man kann jede kontextsensitive in eine monotone Grammatik umwandeln.“ Andersrum, oder?

  3. Vielen Dank euch beiden, ich habe beide Fehler korrigiert (oben kommentarlos, sonst wird’s zu durcheinander). Schlampig, schlampig. Ich habe lange am Text hin- und hergebastelt und es war schon spät. Trotzdem hätte ichw ohl noch einmal korrekturlesen sollen.

  4. Mach doch eine Veröffentlichung draus.
    So wie du es erklärst, versteh ich endlich was. ;-)

  5. „Eine Grammatik ist ein Quintupel“, sagte mein Informatiklehrer immer. Blöderweise hat er das so oft gesagt, dass nur noch der Satz präsent ist, aber nicht mehr die 5 Dinge, die eine Grammatik haben muss. Naja, aber 10 Jahre danach muss man das ja auch nicht mehr wissen. *find*

  6. Danke fürs Lob, Timo. Richtig leicht verständlich ist es natürlich immer noch nicht, und sicher auch nicht für jeden interessant. Aber ich unterrichte dreimal so viel Informatik wie Englisch in in diesem Jahr, das färbt ab.

    Im Lehrplan für die Jahre 11/12, falls da jemand Informatik wählt, sind übrigens 16 Stunden für formale Sprachen vorgesehen, vor allem reguläre und kontextfreie Sprachen, einfache Automaten dazu. Das ist gut machbar. Weitere 10 Stunden beschäftigt man sich mit „Grenzen der Berechenbarkeit“, auch mit dem Unterschied P/NP und dem Halteproblem bei der Turingmaschine, das mich erst dazu gebracht hat, diese Reihe zu schreiben. Ob das in 10 Stunden geht, weiß ich erst, wenn ich einen Blogeintrag dazu verfasst habe.

    Quintupel? Soweit ich weiß, beschreibt man die Grammatik formal als 4-Tupel. Ich kann mir nie merken, in welcher Reihenfolge die Bestandteile kommen. Nachschlagen… G = (N, T, P, S) , wobei auch andere Zeichen üblich sind. (V statt N, Σ statt T.)
    Das ist dann wohl ein (nachschlagen) Quadrupel. Bei mir ist das alles übrigens erst vier Jahre her.

  7. Sehen Sie: Und bevor Herr Rau zu bloggen begann, musste solche Sachen ich mir anhören. Abends. Nach einem Elf-Stunden-Arbeitstag.

  8. hallo herr rau,
    beeinbdruckend, aber auch sperrig,. was sie da schreiben. ich habe ein paar grundsätzliche fragen dazu aufgeworfen, die nix mit inormatik, formaler sprache oder so zu tun haben. sondern die sich um das thema: wie kriege ich in einem lernblog den flow hin? kümmern. sie finden die kommentare unter http://twitter.com/ciffi
    grüße
    christian füller
    p.s. ihr six words ist übrigens ein toller hinweis – ganz anders als die formale sprache

  9. Flow überlasse ich gerne den anderen Leuten. Sperrig? Manche Dinge sind sperrig. Ich sehe mein Blog nicht nur als Lernblog, es erfüllt verschiedene Funktionen.

  10. in 2.2 stimmt doch was nicht.

    auf der rechten Seite ist ein Nonterminal B das nirgendwo „umgewandelt“ wird

    also is gibt kein B -> …

    oder habe ich das Konzept der kontextsensitiven Sprache nicht kapiert?

  11. Doch, das Konzept stimmt schon. Das sollten oben allerdings nicht die Regeln einer vollständigen Grammatik sein, sondern nur Beispiele, wie einzelne Regeln aussehen können – für eine tatsächliche Grammatik wäre es tatsächlich wenig sinnvoll, ein Nonterminal nur auf der rechten Seite einer Regel zu haben.

  12. supi!

    ich schreib meine Proseminararbeit über Chomsky und seine Hierarchie – da ist mir diese Reihe an Blogeinträgen eine unglaubliche Hilfe die schwerverständlichen Primärquellen zu kapieren – danke danke danke !!

    Wann werden die offenen Fragen in Punkt 5. geklärt ?

    Wäre da auch total interessiert dran, weil das wohl das i Tüpfelchen auf meinem Vortrag wäre.

  13. ich hab ein Problem mit deiner Chomsky 3 Definition:

    A -> a | B | aB
    „..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:“

    Das stimmt ja nicht.

    S -> aSb | e

    e = leeres Wort
    Wäre auch ein regulärer Ausdruck also Chomsky 3 mit NT T NT

  14. Offene Fragen in Punkt 5: Vielleicht in den Pfingstferien. Freut mich, wenn dir die Einträge geholfen haben.

    „Das stimmt ja nicht. “

    Doch. Die Regel

    S -> aSb | e

    ist keine Regel einer Grammatik vom Typ Chomsky 3. Allerdings: Die Sprache, die diese Regel beschreibt, ist tatsächlich regulär. Aber selbst wenn sie es wäre: Man kann jede reguläre Sprache auch mit kontextfreien oder kontextsensitiven oder unbeschränkten Regeln beschreiben.

    (Manchmal muss man das tun. Ein beliebig schweres, aber prinzipiell lösbares Problem, das genau eine Lösung hat, kann man mit einer Turing-Maschine/Chomsky-0-Grammatik formulieren. Die Sprache, die dadurch beschrieben wird, besteht zwar nur aus einem Wort. Demnach könnte man die gleiche Sprache auch mit einfachen Regeln beschrieben. Aber solange man die Lösung nicht kennt, geht das eben nicht.)

  15. habe gestern nochmal rescherchiert. Du hast natürlich Recht!

    Es würde mich total freuen, wenn du das in den Pfingstferien hinbekommst ! Wirklich Top.

  16. Vielen Dank für Ihre Blog-Reihe, hat mir geholfen ein thema zu verstehen, bei dem ich daran gezweifelt hatte es zu bewältigen. (auch wenn dieses Danke mehrere Monate nach dem Erscheinen kommt :P)
    Echt hervorragende Arbeit die Sie hier geleistet haben.

  17. Gern geschehen. Das erinnert mich daran, dass ich endlich mal zu Turing-Maschinen vorstoßen muss, ist ja jetzt auch schon wieder ein Jahr her.

  18. Ich bin gerade wieder in diesen Fäden unterwegs, weil ich mit dem Gedanken spiele, meinerseits einen Blogeintrag über einen Typ von Grammatik zu schreiben, der gelinde kontextsensitiv ist – und wo die Grammatiken, madcynic hat’s geahnt, tatsächlich Quintupel sind. :D

    Dabei sind mir noch zwei kleine Dinge aufgefallen:

    „Doch. Die Regel

    S -> aSb | e

    ist keine Regel einer Grammatik vom Typ Chomsky 3. Allerdings: Die Sprache, die diese Regel beschreibt, ist tatsächlich regulär. Man kann jede reguläre Sprache auch mit kontextfreien oder kontextsensitiven oder unbeschränkten Regeln beschreiben. “

    Der letzte Satz stimmt natürlich, die Grammatik da beschreibt allerdings keine reguläre Sprache. Die Sprache ist die aller Strings von a’s gefolgt von gleich vielen b’s, und endliche Automaten können ja nicht zählen…

    Zu einem interessanteren Punkt:

    „Die Grammatik für {alle Zahlen n, für die gilt a^n+b^n=c^n, 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 {1, 2}, aber das weiß man halt auch erst hinterher.“

    S -> 1 | 2

    Alles andere als absurd kompliziert und sie erzeugt genau die richtige Sprache. :D Kann man von dieser Grammatik folglich behaupten, dass sie das Problem (wie heißt es eigentlich?) berechnet?

  19. Ja, da habe ich den Kommentar nicht genau genug gelesen, habe es ausgebessert.

    Zum interessanteren Punkt: gute Frage. Im Prinzip geht es ja auch im Kommentar darum, wenn ich behaupte, man müsse manchmal eine unbeschränkte Grammatik aufstellen, um eine letztlich doch reguläre Sprache zu beschreiben (die zum Beispiel nur endlich ist, wie in dem Beispielproblem – übrigens die Vermutung von Fermat).

    Kann man sagen, dass S -> 1|2 dieses Problem berechnet? Vielleicht geben verschiedene Disziplinen verschiedene Antworten. Zumindest wird dieselbe Sprache beschrieben.
    Ist das analoge Probleme nicht das, ob 2+2=4 wirklich so einfach ist? Natürlich „ist“ 2 und 2 gleich 4, aber 2+2 sind doch auch wieder ganz etwas anderes als 4. Das eine Ergebnis (oder die eine Menge) sind mehr oder weniger kompliziert dargestellt, das andere Ergebnis (oder die andere Menge) zählt einfach auf.

  20. Hm, knifflig. Ich habe jetzt lange darüber nachgedacht, dann bin ich über diesen Satz gestolpert: „Die Grammatik für {alle Zahlen n, für die gilt a^n+b^n=c^n, 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.“

    Ich denke, dass man durchaus vor dem Beweis der Vermutung von Fermat wusste, wie man das berechnen kann. Zum Beispiel kann man alle Ganze-Zahlen-Tripel (a,b,n) durchgehen und für jedes überprüfen, ob die n-te Wurzel aus a^n+b^n eine ganze Zahl ist, und wenn ja, n in den Output übernehmen. Diese Berechnungsvorschrift kann man auch als (absurd komplizierte) Grammatik schreiben. Man wusste halt nur bis zum Beweis der Vermutung nicht, dass diese Grammatik dieselbe Sprache wie S -> 1|2 beschreibt.

    Oder?

  21. Das kommt wohl darauf an, was man unter berechnen steht. Man kann eine Turingmaschine programmieren (oder eben eine Grammatik aufstellen), die auf diese Weise vorgeht und nach und nach alle Zahlen abklappert. Aber so kann man die Sprache nicht berechnen, oder jedenfalls konnte man nicht wissen, ob man sie berechnen kann. Wenn die Maschine ständig rechnet, weiß man ja nie, ob nicht vielleicht doch noch eine Lösung kommt. Und es gibt ja auch noch die korrekten, aber nicht beweisbaren Aussagen in der Zahlentheorie. Aber vermutlich habe ich mich nur unsauber ausgedrückt.

  22. Wenn man schreibt „Die Aussagen “Man kann etwas berechnen” und “Es gibt eine Grammatik, die die entsprechenden Wörter (und nur die) erzeugt” sind äquivalent“, versteht man unter Berechenbarkeit Chomsky 0, also rekursive Aufzählbarkeit, also (positive) Semi-Entscheidbarkeit. Und die ist bei dieser Sprache gegeben, wie die o.a. Berechnungsvorschrift zeigt: Wenn die Fermatsche Gleichung für ein gegebenes n Lösungen hat, wird man auch irgendwann eine Lösung finden.

    Wenn ich mich nicht täusche; ich google mir die nötigen Wissensfetzen gerade nur so zusammen.

  23. Nein, du hast völlig recht, denke ich. Es müsste oben einfach stehen, dass man die Sprache berechnen kann, dass das aber nicht heißt, dass man sagen kann, wie viele Wörter zu ihr gehören.

  24. Danke für die super Erklärungen!
    Ohne Ihre Seite hätte ich das Thema wohl nicht begriffen.
    Es war ein adäquater Vorlesungsersatz ;D

  25. Ich habe lange nach einer Erklärung gesucht warum das Wortproblem für Kontext Sensitive Sprachen entscheidbar ist. Vielen Dank für die hervorragende und ausführliche Darstellung!

  26. Vielen Dank für diesen Super Blog!
    Bin gerade im M.Sc. Wirtschaftsinformatik und muss mich erstmals intensiver mit theoretischer Informatik auseinandersetzen
    Dein Blog hat mir den Einstieg zu diese Thema sehr erleichtert!

  27. Warum ist klar, dass sich für die Sprache {alle Primzahlen} keine kontextfreie Grammatik finden lässt?

  28. >Warum ist klar, dass sich für die Sprache {alle Primzahlen} keine kontextfreie Grammatik finden lässt?

    Danke für die Frage, denn: So im Nachhinein ist mir das überhaupt nicht mehr klar. Es ist lange her, dass ich in der Materie drin war; gut möglich, dass ich auch damals geblufft habe oder es nicht besser wusste.

    Im Gegenteil: Ich habe zumindest eine Quelle gefunden, aber nicht weiter überprüft, die diese Sprache explizit als Beispiel für kontextfreie Sprachen nennt (was aber nicht stimmen muss):
    https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3367686/

    Allerdings habe ich damals wie heute keine weiteren Beispiele gefunden. Die Primzahlen werden zwar häufig als Beispiel für eine Sprache überhaupt genommen; und Turingmaschinen dazu gibt es auch immer wieder — aber zu welchem Chomsky-Typ die Primzahlsprache gehört, das steht fast nirgendwo explizit.

    Der CYK-Algorithmus für das Wortproblem bei kontextfreien Grammatiken liegt in der Laufzeitklasse O(n3 Schritte), mit n als Anzahl der Zeichen; welche Laufzeit haben denn Algorithmen für Primzahltests?

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.