Nach der letzten Frage zu lesen : „Ist das Komplement Kontextfrei?“ ; Ich erinnerte mich an ein ähnliches Problem, das ich nicht widerlegen konnte:
Ist kontextfrei?
Hier müssen sich die beiden Saiten in mindestens zwei Positionen unterscheiden (der Hamming-Abstand muss größer als ).
Es ist kontextfrei, wenn wir fordern, dass (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 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 mit dem regulären kreuzen, erhalten wir eine kontextfreie Sprache, wie von domotorp in seiner Antwort gezeigt; Ein etwas komplexeres mit (eine weitere , um den Überblick zu behalten) legt nahe, dass nicht kontextfrei sein sollte.
quelle
Antworten:
Der Schnittpunkt mitR={0∗10∗10∗10∗∣ 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
R∖L={0a10b10c10d∣b=n/2∨c=n/2∨a+d=n/2} . Daher ist
L={0a10b10c10d∣b≠n/2∧c≠n/2∧a+d≠n/2} . Wir können dies als umschreiben
L={0a10b10c10d∣b>n/2∨c>n/2∨a+d>n/2∨b,c,a+d<n/2} .
Die ersten3 Fälle können leicht überprüft werden, ebenso wie der vierte.
quelle