welle::erd.ferkel

Wir betrachten die Sprachen L₂:={ww|w∈Σ^* } und L₃:={www|w∈Σ^*} über einem beliebigen endlichen Alphabet Σ mit mindestens zwei Buchstaben. Es ist allgemein bekannt (und anhand von Bar-Hillels Lemma leicht zu zeigen), dass keine dieser Sprachen kontextfrei ist — aber gilt das auch für ihre Komplemente?

Die meisten Leute, die bis hierher mitgelesen haben und die Aufgabe noch nicht kennen, raten wahrscheinlich, dass zumindest bei L₃ auch das Komplement nicht kontextfrei ist, versuchen ihr Glück mit dem Lemma von Bar-Hillel oder gar Ogdens Lemma und ärgern sich nach einiger Zeit sehr, denn diese Ansätze scheitern zwangsläufig. Nicht etwa, weil wir hier einen dieser fiesen Fälle haben, in denen schlimmere Sätze als Ogdens Lemma notwendig sind, sondern weil beide Komplemente kontextfreie Sprachen sind.

Eine Grammatik oder eine Automaten für das Komplement von L₂ anzugeben ist eine beliebte und verhältnismäßig einfache Übungsaufgabe, die sich wunderbar zum Aufwärmen für das Komplement von L₃ eignet. Das nämlich fällt fast allen deutlich schwerer, auch wenn man nur eine kleine Idee haben muss.

Viel Spaß damit.