Ist die Ergänzung von {www | …} Kontextfrei?

12

Es ist bekannt , dass das Komplement {wwwΣ} kontextfrei ist. Aber was ist das Komplement {wwwwΣ} ?

domotorp
quelle
1
Ich habe entdeckt, dass dies Satz 4 in P. Dömösi, S. Horváth, M. Ito, L. Kászonyi, M. Katsura ist: Formale Sprachen, die aus primitiven Wörtern bestehen. link.springer.com/chapter/10.1007/3-540-57163-9_15
domotorp

Antworten:

11

Ich glaube immer noch CFL, mit einer Anpassung des klassischen Beweises. Hier ist eine Skizze.

Betrachten Sie L={xyz:|x|=|y|=|z|(xyyz)} , das ist das Komplement von {www} , wobei die Wörter der Länge nicht 0 mod 3 entfernt werden.

Sei L={uv:|u|3|v|30u2|u|/3v|v|/3} . Es ist klar, dass L CFL ist, da Sie eine Position p erraten und berücksichtigen können, dass up/2 endet . Wir zeigen, dass L=L .

  • LL :seiw=xyzL . Angenommen, es gibt einp so dassxpyp . Dann schreibeu für die3p/2 ersten Zeichen vonw undv für den Rest. Natürlichu2|u|/3=xp . Was ist nunv|v|/3 ? Zuerst:

|v|/3=(|w|3p/2)/3=|w|/3p/2.

Daher ist dies in w Position:

|u|+|v|/3=3p/2+|w|/3p/2=|w|/3+p,
oder, mit anderen Worten, die Position p in y . Dies zeigt, dass u2|u|/3=xpyp=v|v|/3 .

Wenn ypzp , dann sei u die erste 32(|w|/3+p)Zeichen vonw, so dassu2|u|/3istyp; vist der Rest vonw. Dann:

|u|+|v|/3=2|w|/3+p
daher ähnlichv|v|/3=zp.

  • LL : Wir kehren den vorherigen Prozess um. Seiw=uvL . Schreiben Siep=2|u|/3 . Dann:
    p+|w|/3=2|u|/3+|uv|/3=|u|+|v|/3.
    Alsowp=u2|u|/3v|v|/3=wp+|w|/3 undwL (da, wennw die Formxxx , muss es gelten, dasswp=wp+|w|/3 für allep ).
Michaël Cadilhac
quelle
2
Wow, unglaublich! Ich behaupte nicht, dass ich jedem Detail Ihres Arguments gefolgt bin, als ob ich nicht sehe, was Sie mit der letzten Zeile ('Für das letzte Bit') meinen oder warum Sie den Fall nicht trennen, wenn , aber Ihre Lösung funktioniert schließlich. Ich würde den Haupttrick als 3 a + 3 b = 2 a + ( b - a ) + 2 a + 2 b zusammenfassen . Der ähnliche Trick funktioniert auch für das Komplement von L r = { w r|w|/3<p/23a+3b=2a+(ba)+2a+2b . Ich frage mich, ob L ' = { x y z : | x | = | y | = | z | ( x y ) } ist kontextfrei oder nicht. Lr={wr}L={xyz:|x|=|y|=|z|(xy)}
Domotorp
1
@domotorp: Prost! Okay, "das letzte bisschen" war unnötig, danke! Was "den Fall betrifft, in dem " ist, bin ich mir nicht sicher, wo Sie das meinen. Habe ich etwas verpasst? Was dein L ' angeht, habe ich mich gefragt, ob ich diesen "Beweis" mache! Ich |w|/3<p/2L
bin
2
Oh mein schlechtes, immer! p/2|w|/3
Domotorp
Wahrscheinlich ist es kein Problem, aber kann ungerade sein, also sollten Sie die Fälle behandeln | u | = 3 p / 2 ( ? ), Wenn p ungerade ist. p|u|=3p/2(?)p
Marzio De Biasi
@ MarzioDeBiasi: Ja, genau deshalb ist dies eine Skizze :-)
Michaël Cadilhac
10

So denke ich über die Lösung dieses Problems mit einem PDA nach. Meiner Meinung nach ist es intuitiv klarer.

xwww|x|0ab|w|

Wir verwenden den üblichen Trick, den Stapel zu verwenden, um eine ganze Zahl beizubehalten, indem wir ein neues " unteren Ende des Stapels" -Symbol , das den absoluten Wert speichert als Anzahl der Zähler auf dem Stapel und sgn ( ) durch den Status des PDA. Somit können wir erhöhen oder verringern, indem wir die entsprechende Operation ausführen.tZ|t|tt

Das Ziel besteht darin, mithilfe des Nichtdeterminismus die Positionen der beiden zu vergleichenden Symbole zu erraten und mit dem Stapel , wobei der Abstand zwischen diesen beiden Symbolen ist. t:=|x|3dd

Wir erreichen dies wie folgt: Erhöhen Sie für jedes Symbol, das angezeigt wird, bis das erste erratene Symbol ausgewählt ist, und zeichnen Sie im Zustand auf. Verringern Sie für jedes nachfolgende Eingabesymbol, bis Sie feststellen, dass Sie gesehen haben , um ( für die Eingabelänge und für die Entfernung). Erraten Sie die Position des zweiten Symbols und notieren Sie, ob . Erhöhen Sie für nachfolgende Eingabesymbole weiter. Akzeptiere, wenn (oben durch erkennbar ) und .taabt213babtt=0Zab

Das Schöne daran ist, dass klar sein sollte, wie dies auf willkürliche Befugnisse ausgedehnt werden kann.

Jeffrey Shallit
quelle
2
In der Tat sehr ordentlich!
Domotorp
1
Ah, viel schöner in der Tat :-)
Michaël Cadilhac
4

Nur eine andere ("grammatikalisch orientierte") Perspektive, um zu beweisen, dass das Komplement von für jedes feste Verwendung von Schließungseigenschaften CF ist .{wk}k

Beachten Sie zunächst, dass es im Komplement von immer so dass . Wir konzentrieren uns auf und beginnen mit einer einfachen CF-Grammatik, die generiert:{wk}iwiwi+1w1w2

L={a00...0w1b00...0w2...000...0wk|wi|=n}={a0n1b0n(k1)1}

Zum Beispiel haben wir für ,k=3L={ab0,a0b000,a00b00000,...}GL={Sab0|aX00,X0X00|0b0}

Wenden Sie dann den Verschluss unter inversem Homomorphismus und Vereinigung an :

Erster Homomorphismus:φ(1)a,φ(0)b,φ(1)0,φ(0)0

Zweiter Homomorphismus:φ(0)a,φ(1)b,φ(1)0,φ(0)0

L=φ1(L)φ1(L) ist immer noch kontextfrei

Wenden Sie den Verschluss unter zyklischen Verschiebungen auf an, um den Satz von Saiten der Länge nicht die Form :Lknwk

L=Shift(L)={uuwk|u|=kn} .

Fügen Sie schließlich den regulären Satz von Zeichenfolgen hinzu, deren Länge nicht durch teilbar ist , um genau das Komplement von :k{wk}

L{{0,1}nnmodk0}={uuwk}

Marzio De Biasi
quelle