Ich wurde von einem Studenten wie folgt gefragt und konnte keine vollständige Antwort finden:
Gibt es Schließungseigenschaften für die Klasse von Sprachen, die nicht kontextfrei sind?
Es ist ziemlich einfach, Beispiele zu finden, die zeigen, dass es nicht unter Schnittmenge und Iteration geschlossen ist (Kleene-Sternoperator), aber wie wäre es mit Vereinigung und Verkettung? Ich vermute, dass es auch nicht geschlossen ist. Wenn ich also nicht weit weg bin, suche ich nach Beispielen für zwei Nicht-CFLs, deren Vereinigung oder Verkettung eine CFL ist.
Antworten:
Es gibt wahrscheinlich nur wenige oder keine "interessanten" und "natürlichen" Schließungseigenschaften für die Klasse von Sprachen, die nicht kontextfrei sind. In der Tat ist das wahrscheinlich wahr für:
Jede Klasse von Sprachen, die durch einen bestimmten Automaten, eine bestimmte Grammatik oder ein bestimmtes Rechenmodell definiert ist - die regulären Sprachen, die cfls, verschiedene Unterklassen der cfls wie die linearen Sprachen und die deterministischen cfls, die kontextsensitiven Sprachen, die begrenzten Sprachen und bald.
Der Grund ist, dass viele, wenn nicht die meisten oder alle "interessanten" Schließungseigenschaften die Fähigkeit haben, eine Sprache drastisch zu vereinfachen, beispielsweise sie auf endliche Mengen oder etwas ähnlich Einfaches abzubilden. Beispielsweise können Sie immer einen konstanten Homomorphismus (h (a) = 0) auf eine nicht kontextfreie Sprache anwenden und die Sprache aller Nullzeichenfolgen abrufen, die kontextfrei ist (tatsächlich regulär). Wenn also die Definition der Klasse bedeutet, dass sie nicht sehr "einfach" ist (wie nicht kontextfrei), führt Sie das Schließen zu "einfachen" Sprachen, dh außerhalb der Klasse.
Dies könnte tatsächlich ein interessantes Forschungsprojekt darstellen, dessen Teil, wie ich vermuten würde, darin bestehen würde, "einfach", "interessant" und "natürlich" auf geeignete Weise zu definieren und auch formale Wege zu finden, um mit trivialen und trivialen Dingen umzugehen entartete Fälle wie der, den ich gegeben habe.
quelle