Ist die Sprache von Wortpaaren gleicher Länge, deren Hamming-Abstand 2 oder mehr beträgt, kontextfrei?

26

Ist der folgende Sprachkontext frei?

L={uxvyu,v,x,y{0,1}+,|u|=|v|,uv,|x|=|y|,xy}

Wie von sdcvvc hervorgehoben, kann ein Wort in dieser Sprache auch als die Verkettung von zwei Wörtern gleicher Länge beschrieben werden, deren Hamming-Distanz 2 oder mehr beträgt.

Ich denke, es ist nicht kontextfrei, aber es fällt mir schwer, es zu beweisen. Ich habe versucht, diese Sprache mit einer regulären Sprache zu schneiden (wie zum Beispiel 0 1 0 1 ), dann habe ich das Pumplemma und / oder die Homomorphismen verwendet, aber ich bekomme immer eine Sprache, die zu kompliziert ist, um sie zu charakterisieren und aufzuschreiben. 0101

Robert777
quelle
Haben Sie versucht, die Zeichenfolge pumpen 0u1x1u0x?
Pål GD
Ja, aber ich habe es nicht geschafft, diese Zeichenfolge aus der Sprache zu entfernen (das bedeutet nicht, dass es nicht möglich ist, nur, dass ich es versäumt habe).
Robert777
1
@ PålGD, du würdest wahrscheinlich eine Möglichkeit brauchen, die Teile zu "markieren", wie 1u01x01u01x0
vonbrand
8
Diese Sprache kann geschrieben werden als {uv:|u|=|v|,d(u,v)2} wobei d die Hamming-Distanz ist. Beachten Sie, dass wenn wir 2 durch 1 ersetzen, dies kontextfrei ist ( cs.stackexchange.com/questions/307 ), der dort verwendete Trick jedoch nicht funktioniert. Persönlich wette ich, dass es nicht kontextfrei ist.
SDCVVC
1
@sdcvvc: Sie haben Recht, man partitioniert das u in ux so dass sich eines der unterschiedlichen Bits in u und das andere in x . Ich stehe korrigiert.
András Salamon

Antworten:

7

Hinweis [30.07.2019] Der Beweis ist falsch ... die Frage ist komplizierter als es klingt.

Nach einem gescheiterten Versuch hier ist es eine andere Idee.

Wenn wir schneiden L mit dem regulären Sprache Lreg=0101010 wir eine CF Sprache erhalten.

Vielleicht können wir mehr Glück haben , wenn wir verwenden Lreg=010101010 (eine Zeichenkette mit genau 4 1s).

Let L1=LLreg , formlos wL1 , wenn es in zwei Teile gespalten Hälften werden kann, so dass eine Hälfte genau enthält {0,1,3,4} 1s oder beiden Hälften zwei enthalten 1 s aber ihre Positionen stimmen nicht überein.

Angenommen, L1 ist CF und sei G seine Grammatik in Chomsky-Normalform, und sei

w=uv=0a10b10c10d10eL1

Wir haben |u|=|v|(gerade Länge) und d(u,v)2

Wenn wir unsere Aufmerksamkeit auf die Art und Weise beschränken, in der die vier Einsen von w erzeugt werden können, haben wir die drei oben in Abbildung 1 gezeigten Fälle. Der zentrale Teil von Abbildung 1 zeigt den ersten Fall (die anderen sind jedoch ähnlich). .

Bildbeschreibung hier eingeben
Abbildung 1 (das vollständige Bild kann hier heruntergeladen werden )

Wenn wir a=e,c=2a und b,da wählen , sehen wir, dass die Nullen zwischen den beiden Einsenpaaren unabhängig voneinander pumpbar sein müssen (rote Knoten in der Abbildung): insbesondere für ausreichend große ba , Wir erhalten einen doppelten nicht-terminalen Knoten in einem internen Teilbaum (Knoten X in Abbildung 2) oder eine wiederholte Teilsequenz auf dem Weg zur ersten oder zweiten 1 (Knoten Y in Abbildung 2). Man beachte , dass 2 ein wenig vereinfacht: Es kann zwischen den zwei Nicht - Terminal - Knoten sein , X s, und auch zwischen den beiden Ys ( Y...Zi...Y aber mitZi ergibt das nur 0s rechts von der ersten 1).

Bildbeschreibung hier eingeben
Figur 2

Wir können also ein willkürliches a=e=k,c=2a festlegen und dann ein ausreichend großes b auswählen , um einen unabhängig pumpbaren Knoten in der Folge von Nullen zwischen der ersten und der zweiten 1 . Für die Folge von Nullen zwischen der dritten und vierten 1 können wir d=b!+b wählen ! + b .
Aber 0b ist unabhängig pumpbar, so dass es einen pb pumpbaren Teilstring y , dh so, dass b=xyz,|y|=p,|x|0,|z|0 undxyiz=b!+b . Die Zeichenfolge, die wir erhalten, ist:

w=0k10b!+b102k10b!+b10k

aber wL1 . Somit ist L1 nicht CF und schließlich ist L nicht CF.

Wenn der Beweis korrekt ist (???), kann er auf jede Sprache Lk={uv:|u|=|v|,d(u,v)k},k2

Vor
quelle
Ich befürchte, dass das Kopfgeld verfällt, bevor wir diesen Beweis tatsächlich überprüfen können. Wenn also in den nächsten 4 Stunden keine drastischen Informationen auftauchen, sind dies die Punkte, die für den bislang besten Versuch sprechen.
jmite
@jmite: Keine Sorge, es besteht die hohe Wahrscheinlichkeit, dass es sich um einen falschen Versuch handelt (der etwa 30 Minuten gedauert hat, bevor ein kleiner Fehler entdeckt wurde) :-) :-)
Vor
Warum die Fallunterscheidung? Die Zweige in der Grammatik haben keine Beziehung zu den Worthälften. Aber ich denke, es spielt keine Rolle; Wenn der Beweis funktioniert, ist diese Fallunterscheidung nicht erforderlich. Eine angenommene Grammatik zu betrachten und den Beweis des Pumping-Lemmas anstelle des Lemmas selbst zu verwenden, ist ein netter Trick (man sollte dies öfter tun). Ich habe eine (echte) Sorge: Wenn Sie eine Teilzeichenfolge von pumpen , erhalten Sie 0 b + p ( i - 1 ) ; Ich verstehe nicht, wie du zu B + B kommst ! . Denken Sie nicht, dass das dem Beweis schaden sollte, aber überprüfen Sie es besser. Vielleicht möchten Sie auch eine Notation (und Tippfehler) korrigieren.0b0b+p(i1)b+b!
Raphael
1
@Raphael: danke für die Kommentare. Vielleicht irre ich mich, aber wenn du als Ziellänge dann für jede Pumplänge p , die Zeichenfolge 0 b kann in zerlegt wird 0 x y z , ( | x y z | = b , | y | = p b ) und kann zu pumpen x y i z = b + b ! in deinem Beispiel ist b sicher geteilt !b+b!p0b0xyz,(|xyz|=b,|y|=pb)xyiz=b+b!b!es gibt also a für die p ( i - 1 ) = b ! , aber die ursprüngliche Stringlänge ist b , die Gesamtpumplänge ist also | x y ( i - 1 ) z | = b + b ! . Ich erinnere mich an ein paar Übungen, die das Lemma des Ogden verwenden ... jetzt werde ich sie noch einmal überprüfen. (i1)p(i1)=b!b|xy(i1)z|=b+b!
Vor dem
@Raphael: ... Ich habe nirgendwo einen Beweis gefunden, sondern nur eine Arbeit von Zach Tomaszewski, die beweist, dass die Ergänzung von CF ist (siehe Frage ), also ist es vielleicht ein neues Ergebnis (wenn auch einfach); und ein Pump-Lemma-Stil-Theorem kann für Sprachen mit Zeichenfolgen abgeleitet werden, die eine endliche Anzahl eines bestimmten Symbols und Teilzeichenfolgen beliebiger Länge dazwischen enthalten. Ldup={ww}
Vor dem
2

Nach 2 fehlgeschlagenen Versuchen, die von @Hendrik Jan abgelehnt wurden (danke), ist hier ein weiterer, der nicht erfolgreicher ist. @Vor hat ein Beispiel für eine deterministische CF-Sprache gefunden, bei der die gleiche Konstruktion angewendet würde, wenn sie korrekt wäre. Dies ermöglichte es, einen Fehler bei der Verankerung des Strings in der Anwendung des Lemmas zu identifizieren . Das Lemma selbst scheint nicht schuld zu sein. Dies ist eindeutig eine zu vereinfachende Konstruktion. Weitere Details finden Sie in den Kommentaren.y


Die Sprache ist nicht kontextfrei.L={uxvyu,v,x,y{0,1}{ϵ} , u∣=∣v , uv , x∣=∣y , xy }

Es ist hilfreich, die Charakterisierung berücksichtigen u | = | v | , d ( u , v ) 2 } wobei d die Hamming-Distanz ist, vorgeschlagen von @sdcvvc. Woran man denken muss, sind 2 ausgewählte Positionen in jeder halben Saite, so dass sich die entsprechenden Symbole unterscheiden.L={uv:|u|=|v|,d(u,v)2}

Dann betrachten Sie eine Zeichenkette so, dass i < j und i + j gerade sind. Es ist eindeutig in der Sprache L, indem u und x irgendwo zwischen den beiden Einsen geschnitten werden. Wir wollen diese Zeichenkette im ersten Teil zwischen den Einsen pumpen, damit sie 10 j 10 j wird, was nicht in der Sprache sein soll.10i10ji<ji+jux10j10j

Wir versuchen zunächst, Ogdens Lemma zu verwenden , das dem Pump-Lemma ähnelt, aber auf oder mehr auffällige Symbole angewendet wird , die in der Zeichenfolge markiert sind, wobei p die Pumplänge für markierte Symbole ist (aber das Lemma kann mehr pumpen, weil es auch pumpen kann nicht markierte Symbole). Die Pumplänge p hängt nur von der Sprache ab. Dieser Versuch wird fehlschlagen, aber der Fehler wird ein Hinweis sein.ppp

Wir können dann wählen und Symbole in der ersten Folge von i 0 markieren . Wir wissen, dass keine der beiden Einsen in der Pumpe sein wird, weil sie einmal herauspumpen kann (Exponent 0), anstatt hinein zu pumpen. Und das Herauspumpen der Einsen würde uns aus der Sprache bringen.i=pi

Wir könnten jedoch auf beiden Seiten der zweiten 1 genauso schnell oder sogar schneller auf der rechten Seite pumpen, so dass die zweite 1 niemals durch die Mitte der Saite gelangen würde. Auch Ogdens Lemma legt keine Obergrenze für die Größe des zu pumpenden Materials fest, so dass es nicht möglich ist, das Pumpen so zu organisieren, dass die genaueste 1 genau in der Mitte der Saite liegt.

Wir verwenden eine modifizierte Version des Lemmas, hier Nash's Lemma genannt, die diese Schwierigkeiten bewältigen kann.

Wir brauchen zuerst eine Definition (es hat wahrscheinlich einen anderen Namen in der Literatur, aber ich weiß nicht welche - Hilfe ist willkommen). Eine Zeichenkette wird als Löschen einer Zeichenkette v bezeichnet, wenn sie aus v durch Löschen von Symbolen in v erhalten wird . Wir werden u v beachten .uvvvuv

Nashs Lemma: Wenn eine kontextfreie Sprache ist, gibt es zwei Zahlen p > 0 und q > 0, so dass für jede Zeichenfolge w mit einer Länge von mindestens p in L und für jede Art, p oder mehr der Zeichenfolgen zu „markieren“, gilt Positionen in w , w können wie folgt geschrieben werden: w = u x y z v mit der Zeichenfolge u , x , y , z , v , so dassLp>0q>0wpLpwww=uxyzvuxyzv

  1. hat mindestens eine markierte Position,xz
  2. hat höchstens p markierte Positionen undxyzp
  3. es gibt 3 Strings x , y , z derart , daß x^y^z^
    1. , yy, zz,x^xy^yz^z
    2. , 1 | y | q , und1≤∣x^z^∣≤q1≤∣y^∣≤q
    3. ist in L für jedes i 0 und für jedes j 0 .uxjx^iy^z^izjvLi0j0

Beweis : Ähnlich wie der Beweis von Ogdens Lemma, jedoch werden die Teilbäume, die den Zeichenfolgen und x z entsprechen, so beschnitten, dass sie keinen Pfad mit dem doppelten gleichen nicht-terminalen Wert enthalten (mit Ausnahme der Wurzeln dieser beiden Teilbäume). Dies notwendigerweise begrenzt die Größe der erzeugten Zeichenfolge x z und y durch eine Konstante q . Die Zeichenfolgen x j und z j für j 0 , die einer unbeschnittenen Version des Baums entsprechen, werden hauptsächlich mit j = 1 verwendetyxzx^z^y^qxjzjj0j=1 Vereinfachung der Rechnungslegung bei Anwendung des Lemmas.

Wir ändern den obigen Beweis Versuch die Markierung ganz links Symbole 0, aber sie werden von gefolgt 2 q Symbole 0 , um sicherzustellen , dass wir im linken Teil des Strings, zwischen den beiden 1 der Pumpe. Dass insgesamt machen i = p + 2 q 0'en zwischen der 1'en (tatsächlich i = p + q wäre ausreichend, da die am weitesten rechts liegenden 1 nicht sein kann , z , die einfach zu entfernen erlauben würden).p2qi=p+2qi=p+qz^

Was bleibt, ist gewählt zu haben, damit wir genau die richtige Anzahl von Nullen pumpen können, so dass die beiden Sequenzen gleich sind. Bisher besteht die einzige Einschränkung für j darin, größer als i zu sein . Und wir wissen auch, dass die Anzahl der Nullen, die bei jedem Pumpen gepumpt werden, zwischen 1 und q liegt. Also sei h Produkt der ersten q ganzen Zahlen. Wir wählen j = i + h .jjihqj=i+h

Da das Pumpinkrement - was auch immer es ist - in [ 1 , q ] ist , teilt es h . Sei k der Quotient. Wenn wir genau k- mal pumpen , erhalten wir einen String 10 j 10 j, der nicht in der Sprache ist. Daher ist L nicht kontextfrei.d[1,q]hkk10j10j

.

Ich denke, ich werde niemals
eine Schnur sehen, die so schön ist wie ein Baum.
Wenn es keine Syntaxanalyse gibt, ist
die Zeichenfolge nichts anderes als eine Farce

babou
quelle
Beachten Sie jedoch, dass der Durchlauf über die zweite Hälfte den Stapel in umgekehrter Reihenfolge liest. Das scheint zu bedeuten, dass die beiden Positionen in beiden Hälften in der gleichen Position sind, aber umgekehrt?
Hendrik Jan
du hast recht ... ich habe gepatzt ... jetzt weiß ich, was mich am Hinterkopf gequält hat.
Babou
Ich erkannte das Argument (weil ich es nicht zum Laufen bringen konnte, als ich es selbst versuchte).
Hendrik Jan
Soll ich diese falsche Antwort hinterlassen? Es ist irgendwie hilfreich, denke ich, da es das Problem verdächtig ähnlich macht wie . Das Problem ist, dass die Regeln der Website nicht dazu führen sollen, dass falsche Ergebnisse zur Diskussion gestellt werden (ich meine, ich mag Downvotes nicht mehr als jeder andere). aibjckaibjck
Babou
@HendrikJan Hab ich nochmal gepatzt? (Übrigens, danke für die Diskussion)
babou
-1

Durch diese Frage denke ich, dass kontextfrei ist und durch die folgende Grammatik erzeugt wird LSAXBYBYAXA00A00A11A01A1B10B00B11B01B1X00X00X11X01X1Y10Y00Y11Y01Y1

MK Dadsetani
quelle
4
Das ist falsch; Sie können nicht schützen, dass die Länge von AX der Länge von BY entspricht. Beispielsweise generiert Ihre Grammatik S -> AXBY -> A011 -> 0A1011 -> 001011, das nicht in der Originalsprache vorliegt. Außerdem erzeugen Ihre Symbole A und X dieselbe Sprache wie B und Y; Sie können zusammengelegt werden.
SDCVVC