Ist {ww '| HamDist (w, w ')> 1} kontextfrei?

13

Nach der letzten Frage zu lesen : „Ist das Komplement {www...} Kontextfrei?“ ; Ich erinnerte mich an ein ähnliches Problem, das ich nicht widerlegen konnte:

Ist L={www,w{0,1}|w|=|w|HamDist(w,w)>1} kontextfrei?

Hier müssen sich die beiden Saiten in mindestens zwei Positionen unterscheiden (der Hamming-Abstand muss größer als 1 ).

Es ist kontextfrei, wenn wir fordern, dass HamDist(w,w)1 (dh die beiden Zeichenfolgen müssen einfach unterschiedlich sein).

Ich vermute, dass die Sprache nicht kontextfrei ist: Wenn wir sie mit den regulären Werten 0101010 kreuzen, erhalten wir Fälle, in denen sich ein PDA nach Erreichen der Hälfte der Zeichenfolge zwei Positionen in umgekehrter Reihenfolge "merken" sollte.

Update: Wenn wir L mit dem regulären R={0101010} kreuzen, erhalten wir eine kontextfreie Sprache, wie von domotorp in seiner Antwort gezeigt; Ein etwas komplexeres LR mit R={01010101010} (eine weitere 1 , um den Überblick zu behalten) legt nahe, dass L nicht kontextfrei sein sollte.

Marzio De Biasi
quelle
ist eigentlich einfacher, da es genau die Wörter sind, die nicht von der Form w w sind (geschnitten durch R ' ). LRwwR
Domotorp
@domotorp: richtig! geändert in ungerade feste s (sofern Ihre Antwort nicht auch an { ( 0 1 0 ) k } angepasst werden konnte , für jede feste ungerade k )1{(010)k}k
Marzio De Biasi
Ein letzter Kommentar: Es hilft nicht, mit führenden Nullen zu beginnen, da kontextfreie Sprachen für alle Arten von zyklischen Verschiebungen geschlossen sind. Sie könnten sie einfach auf den Stapel schieben, den letzten mit einem speziellen Symbol markieren, den Rest des Algorithmus so tun, als würde der Stapel dort beginnen, und ihn am Ende leeren. (Dies verwendet Übergänge, aber das ist auch einfach, dass solche PDAs denen ohne äquivalent sind.)ϵ
domotorp
Es könnte einfacher sein, über das {0,1,2} Alphabet nachzudenken und Zeichenfolgen mit genau zwei Einsen und zwei Zweisen zu betrachten. Es ist nicht in Ihrer Sprache, wenn der Abstand zwischen 1s und der Abstand zwischen 2s beide n sind.
Kaveh

Antworten:

4

Der Schnittpunkt mit R={0101010 selbst Länge Worten } ist kontextfrei, weil ein PDA kann zwei Positionen erinnern, in einer Art und Weise. Wie auch immer, lassen Sie uns zuerst sehen, was diese Sprache L ist. Sein Komplement ist RL={0a10b10c10db=n/2c=n/2a+d=n/2} . Daher ist L={0a10b10c10dbn/2cn/2a+dn/2} . Wir können dies als umschreiben L={0a10b10c10db>n/2c>n/2a+d>n/2b,c,a+d<n/2} .

Die ersten 3 Fälle können leicht überprüft werden, ebenso wie der vierte.

b>n/2 : Legen Sie den Stapel bis zur ersten 1 ein und beginnen Sie dann, vom Stapel zu springen, bis er nicht mehr leer ist. Nachdem es leer ist, lege es wieder in den Stapel, bis wir die zweite 1 erreichen. Von da an lege den Stapel auf.

c>n/2 : Gleich.

a+d>n/2 : Legen Sie den Stapel bis zur ersten 1 ein und beginnen Sie dann, vom Stapel zu springen, bis er nicht mehr leer ist. Nachdem es leer ist, lege es wieder in den Stapel, bis wir die dritte 1 erreichen. Von da an lege den Stapel ab.

b,c,a+d<n/2 : Legen Sie den Stapel bis zur ersten 1 ein und beginnen Sie dann, vom Stapel zu springen, bis er nicht mehr leer ist. Nachdem es leer ist, lege es wieder in den Stapel, bis wira+n/2 (nicht deterministisch erraten, irgendwo zwischen der zweiten und dritten 1). Von da an platziere den Stapel.

domotorp
quelle
Danke domotorp, ich lese deine idee; Ich denke, ist { 0 a 1 0 b 1 0 c ' 0 c' ' 1 0 d( n / 2 = a + b + c ' = c '' + d + 1 ) [ ( a = c '' ) ( c = d ) }RL{0a10b10c0c10d (n/2=a+b+c=c+d+1)[(a=c)(c=d)} (two 1s on the left half) union its reverse (two 1s on the right half). So how do you get b=n/2c=n/2a+d=n/2?
Marzio De Biasi
RL is that the HamDist is at most 1. This happens exactly if two of the three 1's match, i.e., one is in the same position in the first half, as the other is in the second half. If these two 1's are the first and second 1's, then we get b=n/2, if they are the second and third 1's, we get c=n/2, and if they are the first and third 1's, we get b+c=n/2, or equivalently, a+d=n/2 (where I'm cheating a bit with some constant ±1's).
domotorp
Does this answer the full question?
Michaël Cadilhac
@domotorp: ok I got it, thanks! Another doubt: from LR={...bn/2cn/2...} (which is ok) you write LR={...b>n/2c>n/2b,c<n/2} but, is it equivalent to: LR={...(b<n/2b>n/2)(c<n/2c>n/2)}? (a+d condition omitted)
Marzio De Biasi
@Michael: No.  
domotorp