Wenn L kontextfrei ist, muss FH (L) kontextfrei sein?

7

Definieren FH(L)={xΣ:yΣ with |x|=|y| such that xyL}. Mit anderen Worten,FH(L) ist die Menge der ersten Hälften von Saiten gleicher Länge in L. Vor diesem Hintergrund, wennL ist kontextfrei, muss FH(L) kontextfrei sein?

Hier ist mein Beweisversuch:

Schon seit L Ist eine CFL vorhanden, gibt es eine nicht deterministische PDA-Erkennung L, M=(Q,Σ,Γ,δ,q0,Z0,F), wo Σ ist das Eingabealphabet, Γ ist das Stapelalphabet und Z0ist das Symbol für den anfänglichen Stapelinhalt. PDA konstruierenM von Mmit M=(Q,Σ,Γ,δ,q0,Z0,F), wie folgt definiert:

Q=q0(Q×Γε)×(Q×Γε)×(Q×Γε).

F={[(q,X),(q,X),(p,Y)]:X,YΓε and pF}

δ(q0,ε,ε)={([(q,X),(q0,Y),(q,X)],ε):qQ and X,YΓε}

δ([(q,X),(p,Y),(r,Z)],a,ε)={([(q,X),δ(p,a,Y),δ(r,b,Z)],ε):X,Y,ZΓε  and bΣ}

Die erste Komponente eines Staates in Q zeichnet den erratenen Zustand auf qund ändert sich nicht, sobald es anfänglich aufgezeichnet wurde. Das zweite Element zeichnet auf, in welchem ​​Zustand wir uns befinden, nachdem wir ein Präfix der Eingabe x verarbeitet haben, beginnend mit dem Zustandq0und das dritte Element zeichnet auf, in welchem ​​Zustand wir uns befinden, nachdem wir ein Präfix des erratenen verarbeitet haben y, ab q.

Ich bin mir nicht sicher, ob dieser Beweis funktioniert, da ich etwas verwirrt bin, was ich mit dem Stack machen soll M.

David Smith
quelle
Was denken Sie?
Yuval Filmus
Nun, ich vermute, dass ein Automat, der FH (L) erkennt, nicht mehr Speicher benötigt als ein Automat, der L erkennt.
David Smith
Haben Sie versucht, Ihren Verdacht zu beweisen? Wo bist du festgefahren?
Yuval Filmus
Ich werde meinen Beweisversuch als Antwort schreiben, damit Sie einen Kommentar abgeben können.
David Smith
"Ich bin nicht sicher, ob dieser Beweis funktioniert, weil ich etwas verwirrt bin, was ich mit dem Stapel machen soll M"- das ist der Kern des Problems und lässt mich glauben, dass es ein Gegenbeispiel gibt, obwohl mir keines einfällt. Das Problem ist, dass Sie simulieren müssen MGleichzeitig wird gezählt, wie viele Symbole Sie gesehen haben und wie viele noch übrig sind.
Yuval Filmus

Antworten:

7

Die in den Kommentaren entwickelte Intuition ist richtig. Die Antwort lautet NEIN, es gibt ein Gegenbeispiel, eine CFL, für die die ersten Hälften keine CFL sind.

L={ambncna3mm,n1}über dem Alphabet {a,b,c}, aus der Antwort auf unserer Schwesterseite .

Beweis durch Pumping Lemma: Pick apbpcpFH(L);; Pumpen zerstört entweder die "bncn"- oder die" erste Hälfte "-Eigenschaft.

Eine leichte Anpassung dieser Sprache ist K={ambncn##a3mm,n1}über dem Alphabet {a,b,c,#}. Wir können jetzt den Punkt "erzwingen", an dem sich die Schneidstelle der ersten Hälfte befindet, und eine andere Proof-Technik erhalten.

Lassen H=FH(K)abc#. Dies bedeutet, dass wir nur die ersten Hälften betrachten, in denen sich die Mitte genau an dem Punkt zwischen den beiden befindet#-Symbole. Somit.m+2n+1=1+3m, oder m=n. SomitH={anbncnn1}#. Nun wennK ist dann kontextfrei Hist kontextfrei (über den Schnittpunkt der Closure-Eigenschaft durch reguläre Sprachen). Diese Sprache ähnelt einem nicht kontextfreien Standardbeispiel{anbncnn1}. Dies kann wiederum durch rechten Quotienten mit erhalten werden#das bewahrt auch die Kontextfreiheit .

Hendrik Jan.
quelle
Ich habe die Beweisidee hinzugefügt (aus der unter Mathematik verlinkten Quelle, damit der Wert dieser Antwort nicht von der Verfügbarkeit dieser Ressourcen abhängt.
Raphael
@ Raphael Danke. Ich habe einen Text hinzugefügt, um die spezifische Verwendung des Zusatzes zu erläutern#-Zeichen, das ich eingeführt habe.
Hendrik
Ah, jetzt sehe ich, wohin du damit gegangen bist. Nett!
Raphael