Definieren . Mit anderen Worten, ist die Menge der ersten Hälften von Saiten gleicher Länge in . Vor diesem Hintergrund, wenn ist kontextfrei, muss kontextfrei sein?
Hier ist mein Beweisversuch:
Schon seit Ist eine CFL vorhanden, gibt es eine nicht deterministische PDA-Erkennung , , wo ist das Eingabealphabet, ist das Stapelalphabet und ist das Symbol für den anfänglichen Stapelinhalt. PDA konstruieren von mit , wie folgt definiert:
.
Die erste Komponente eines Staates in zeichnet den erratenen Zustand auf und ä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 Zustandund das dritte Element zeichnet auf, in welchem Zustand wir uns befinden, nachdem wir ein Präfix des erratenen verarbeitet haben , ab .
Ich bin mir nicht sicher, ob dieser Beweis funktioniert, da ich etwas verwirrt bin, was ich mit dem Stack machen soll .
quelle
Antworten:
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.
Eine leichte Anpassung dieser Sprache istK={ambncn##a3m∣m,n≥1} ü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.
quelle