Sprachen, die wir nicht als kontextfrei (dis) beweisen können

21

Ich suche nach Sprachen, die "wahrscheinlich nicht kontextfrei" sind, aber wir können sie mit bekannten Standardtechniken nicht (dis) beweisen.

Gibt es eine aktuelle Umfrage zu diesem Thema oder einen offenen Problembereich einer aktuellen Konferenz?

Wahrscheinlich gibt es nicht viele Sprachen, von denen nicht bekannt ist, dass sie CF sind. Wenn Sie eine Sprache kennen, können Sie sie auch als Antwort posten.

Die Beispiele, die ich gefunden habe, sind:

Hinweis : Wie Aryeh in seiner Antwort gezeigt hat, können Sie eine ganze Klasse solcher Sprachen aufbauen, wenn Sie eine Sprache mit einer unbekannten Vermutung über die (Nicht-) Endlichkeit oder (Nicht-) Leere einiger Mengen "verknüpfen" (z. B. kann nicht als Summe zweier Primzahlen ausgedrückt werden ). Solche Beispiele interessieren mich nicht so sehr.LGOldbeinch={12n2n}

Marzio De Biasi
quelle
1
Für Ihr zweites Beispiel habe ich einen Artikel aus meiner Antwort geschrieben, der gerade geprüft wird (und das erste Feedback war positiv): arxiv.org/abs/1901.03913
domotorp
Es gibt viele Varianten des ersten Beispiels, von denen nicht bekannt ist, dass sie kontextfrei sind. Ich weiß nicht, ob Sie sie als separate Beispiele einfügen möchten. siehe Kapitel 10 des verlinkten Buches (Kászonyi-Katsura-Theorie).
Domotorp
@domotorp: Ich habe es mir nur angeschaut (ich lese immer noch Kapitel 2) ... sie scheinen mir eher technische Versuche zu sein, das Hauptproblem anzugreifen.
Marzio De Biasi

Antworten:

14

Ein weiteres gutes ist das Komplement der Menge S zusammenhängender Unterwörter (auch "Faktoren" genannt) der Thue-Morse-Folge t=0110100110010110 . Um einige Kontext zu geben, erwies sich Jean Berstel , dass das Komplement der Menge T von Präfixen des Thue-Morse Wort ist kontextfrei (und tatsächlich etwas allgemeiner als das). Das entsprechende Ergebnis für Unterwörter ist jedoch noch offen.

Jeffrey Shallit
quelle
Vielen Dank! Wenn Sie es irgendwo angegeben haben (vielleicht in einem Ihrer vielen Artikel über die Thue-Morse-Sequenz? ;-), können Sie den Verweis hinzufügen (auch wenn er in der Form des iterierten Morphismus angegeben ist).
Marzio De Biasi,
12

Wie wäre es mit der Sprache LTP der Doppelprimzahlen? Das heißt, alle Paare natürlicher Zahlen (p,p) (beispielsweise unär dargestellt), so dass p,p beide Primzahlen sind und p=p+2 ? Wenn die Vermutung der doppelten Primzahlen wahr ist, dann ist LTP nicht kontextfrei; sonst ist es endlich.

Edit: Lassen Sie mich kurz skizzieren, dass die Vermutung der Doppelprimzahlen impliziert, dass LTP nicht kontextfrei ist. Ordnen Sie jeder Sprache L ihre Längenfolge 0ein1ein2 , wobei die ganze Zahl in der Folge erscheint, wenn es in L ein Wort der Länge . Es ist eine Konsequenz des (der) Pump-Lemma (s), dass für L , die regulär oder CFL sind, die Längensequenz die Eigenschaft der begrenzten Differenzen erfüllt: Es gibt ein R > 0, so dass ein n +LLR>0einn+1-einnRfür allen. Es ist eine einfache und bekannte Tatsache in der Zahlentheorie, dass die Primzahlen keine begrenzten Unterschiede aufweisen. Schließlich muss jede unendliche Folge einer Sequenz, die die Eigenschaft der begrenzten Unterschiede selbst verletzt, diese verletzen.

Aryeh
quelle
3
Nett, danke! Aber Sprachen, die mit unbekannten Vermutungen über die (Nicht-) Endlichkeit einiger Mengen zusammenhängen, interessieren mich nicht so sehr. Übrigens, wenn diese Vermutungen wahr sind, ist die resultierende Sprache auch regelmäßig :-)
Marzio De Biasi
Wenn es unendlich viele Doppelprimzahlen gibt, wie sehen Sie dann, dass regelmäßig ist? LTP
Aryeh
1
Wenn es unendlich viele Doppelprimzahlen gibt, wie zeigen Sie dann, dass nicht kontextfrei ist? LTP
Emil Jeřábek unterstützt Monica
1
Oh, tut mir leid, ich habe nicht bemerkt, dass Sie die Zahlen in unary darstellen. Dann ist es klar. (Ich glaube, dass der Nachweis dieser binären Repräsentation einen beträchtlichen Fortschritt in Bezug auf die Doppelprimus-Vermutung erfordern würde.)
Emil Jeřábek unterstützt Monica
5
Im Gegenteil, Emil, der "Standard" Beweis, dass die Primzahlen in der Binärdatei nicht kontextfrei sind, reicht aus, um zu beweisen, dass jede unendliche Menge von Primzahlen nicht kontextfrei ist. Wenn es also unendlich viele Doppelprimzahlen gibt, ist das Ergebnis unmittelbar.
Jeffrey Shallit