Ich versuche zu beweisen, dass das Komplement von {a^ib^ic^i} kontextfrei ist

Question

Ich versuche zu beweisen, dass das Komplement von L = {a^ib^ic^i: i> = 1} ist ein Kontext frei. L Komplement ist: {w ist ein Wort über {a, b, c} *: w nicht in L}.

Wie wir wissen, sind kontextfreie Sprachen unter Union geschlossen. Also versuche ich meine Sprache (Komplement von {a^i^i^i}) in kontextfreie Teilmengen aufzuteilen, in denen ihre Vereinigung kontextfrei sein muss. Kann mir jemand helfen, die Teilmengen zu finden? Jedes Mal, wenn ich es versuche, lande ich bei L *!

Vielen Dank.

Answer 1

Hinweis: Im Folgenden verließ ich die Einschränkung aus, dass L nicht die leere Zeichenfolge nicht enthalten, aber das erfordert nur eine kleine Anpassung.

---

Betrachten aibjck. Wenn Sie i=j und j=k haben, dann haben Sie aibici. Umgekehrt, wenn i≠j oder j≠k, dann haben Sie die Ergänzung aibici.

Mit anderen Worten,

L = { aibjck | i=j } ∩ { aibjck | j=k }

und

L' = { aibjck | i≠j } ∪ { aibjck | j≠k }

Es ist einfach, dass jeder Teilmenge in den obigen Gleichungen zu zeigen, ist kontextfrei. Wie Sie sagen, sind kontextfreie Sprachen unter Union geschlossen, aber sie sind nicht unter Kreuzungen geschlossen. folglich ist L' kontextfrei, obwohl L nicht ist.