Angenommen, wir haben eine Sprache L, die kontextfrei ist, und "a" gehört unter anderem zu seinem Alphabet. Wie kann ich beweisen, dass die Sprache ERASEa (L), die alle Instanzen des Zeichens 'a' in den von L erzeugten Strings (zB abbac -> bbc) entfernt, noch kontextfrei ist? Vielen Dank im Voraus!Wie kann ich eine Sprache kontextfrei beweisen, wenn ich einen Buchstaben aus dem Alphabet entferne?
Mein Ansatz wäre, dass wenn L eine kontextfreie Sprache ist, gibt es einige Grammatik G = (V, Σ, R, S). Die Menge der Anschlüsse V und das Startsymbol S bleiben unverändert. Die Menge der Enden, Σ, wird zu Σ '= Σ -' a '. Schließlich wird die Menge der Produktionsregelbeziehungen R = V -> (V ≥ Σ) * so modifiziert, dass R '= V -> (V ≥ Σ') *, wobei die Regeln in R 'nur diejenigen in R mit' a sind 'entfernt. Da G '= (V, Σ', R ', S) eine gültige CFG ist, ist das L ohne' a 'eine kontextfreie Sprache.
Ich nehme an, dass dieses Problem von einem Kurs kommt, den Sie selbst nehmen oder studieren. Es ist schwer zu glauben, dass Ihr Lehrbuch nicht einige Hinweise enthält, wie man diesen Beweis erstellt, aber es ist einfach genug, Referenzen online zu finden. Sie können mit [wikipedia] (https://en.wikipedia.org/wiki/String_operations#String_substitution) und dem folgenden Abschnitt beginnen. (Der Beweis besteht darin, eine Grammatik für die neue Sprache zu konstruieren, indem man die alte Grammatik modifiziert und dann nachweist, dass die konstruierte Grammatik korrekt ist.) – rici