Ich suche eine kontextsensitive Grammatik, die die folgende Sprache beschreibt: .
Ich habe Probleme mit der Tatsache, dass keine Regeln wie erlaubt sind und ich daher kein Nichtterminal platzieren kann, das die "Mitte" des Wortes angibt. Gibt es einen Trick für das Problem?
Antworten:
In der Tat gibt es einen einfachen Trick, mit dem Sie an einer bestimmten Position zusätzliche Informationen hinzufügen können: Ersetzen Sie einfach einen Buchstaben neben der Position und markieren Sie ihn mit den Informationen und dem Originalbuchstaben.
In Ihrem Beispiel haben Sie ein nicht-terminales für die Mitte, aber da es nicht gelöscht werden kann, zählt es auch als normaler Buchstabe. Wir haben also zwei Kopien und , um die ersetzten Buchstaben anzuzeigen. Am Ende der Ableitung sollten die Marker durch ihren Buchstabeninhalt ersetzt werden, durch einfache Produktionen wie .M Ma Mb Ma→a
In den meisten Fällen muss die Anwendung von am Ende des Ableitungsprozesses durchgeführt werden. In einigen Konstruktionen muss dies nicht "zeitgesteuert" sein: Wenn das zu früh verschwindet, kann die Ableitung keine richtige Position finden und der Prozess wird nicht erfolgreich gestoppt. In anderen Fällen braucht man eine Art Kontrolle. Dies geschieht manchmal durch Einführen eines Nichtterminals als Signal, das sich entlang der Buchstaben bewegt. Auch dieses Signal sollte ein Terminal tragen, da Sie sonst die gleichen Probleme haben.Ma→a M
Das Verschieben von Informationen ist in sogenannten monotonen Grammatiken ( mit ) unter Verwendung von Regeln wie , die als Springen über angesehen werden können, einfach . Für korrekte kontextsensitive Grammatiken muss dies in drei Schritte unterteilt werden: . In jeder Produktion wird ein Buchstabe in einem geeigneten Kontext geändert. Es erfordert einige Vorstellungskraft, um zu sehen, dass dieser Prozess nicht mit anderen Teilen der Ableitung interagiert. Was passiert beispielsweise, wenn das im letzten Schritt zuerst an einem anderen Ableitungsschritt beteiligt ist?α→β |α|≤β| XA→AX X A XA→XAX,XAX→AAX,AAX→AX A
Dies funktioniert möglicherweise nicht für sehr kurze Wörter, wenn mehr Informationen als Positionen verfügbar sind. Die einfachste Lösung besteht darin, kurze Zeichenfolgen in Ihrer Konstruktion zu ignorieren und separat zu generieren.
quelle
Kurze Standardantwort: Erstellen Sie einen LBA, der die Sprache akzeptiert, und verwenden Sie die Simulation, um zu beweisen, dass kontextsensitive Grammatiken und LBA denselben Satz von Sprachen definieren. Aber das ist natürlich nicht das, wonach Sie suchen.
Versuchen Sie in diesem speziellen Fall, eine rechtslineare Grammatik für zweimal zu verwenden, eine für die linke und eine für die rechte Hälfte. Alles, was Sie tun müssen, um sicherzustellen, dass beide Grammatiken "synchron" abgeleitet werden.Σ∗
Dies kann durch Vertauschen eines Kontrolltokens erfolgen. Das heißt, die linke Grammatik wählt eine Regel aus, generiert das passende Steuerelement-Token und übergibt es an die rechte Grammatik. Die richtige Grammatik sieht das Steuerelement-Token und führt die Anpassungsregel aus. Beachten Sie, dass Sie auf diese Weise auch eine bidirektionale Kommunikation implementieren können, dies ist hier jedoch nicht erforderlich.
Bei kontextsensitiven Grammatiken gibt es ein Problem: Sie können niemals Nicht-Terminals löschen (außer wenn das leere Wort in der Sprache ist). Daher müssen wir nur so viele Nicht-Terminals erstellen, wie wir benötigen werden. Keiner kann redundant sein.S→ε
Eine Möglichkeit, dies zu erreichen, besteht darin, den gleichen Trick wie für bestimmte Beweise für LBA zu verwenden: Generieren Sie alle Nicht-Terminals, die Sie zuerst benötigen , dh bereiten Sie das "Band" vor. Bewegen Sie sich später auf diesem Band. Ersetzen Sie nur "am Ende" alle Nicht-Terminals durch Terminals.
Sehen Sie, wie Sie dies auf ? Funktioniert es auch für ? Können Sie dieselbe Konstruktion für jedes für reguläres ?Lk={wk∣w∈Σ∗} L=⋃i≥1Lk Lk L
quelle
Obwohl ich nicht weiß, wie die kontextsensitive Grammatik aussehen wird, können Sie Ihr Problem mit dem Symbol wie folgt umgehen .X
Sie wissen, dass Ihre verketteten Wörter mindestens die Länge . Daher können Sie diese Regeln Ihrer Grammatik einfach nach folgenden Regeln "codieren" : | w | ≥ 1 ε a X a → a a , a X b → a b , b X a → b a , b X b → b bw |w|≥1 ε
Ich kann die Gesamtlösung jedoch noch nicht sehen, da es meiner Meinung nach so aussieht, als würden Ihre linken Seiten Ihrer Grammatikregeln möglicherweise beliebig lang, weil ich denke, Sie würden versuchen, die Präfixe von irgendwie in Ihren Regeln zu berücksichtigen .w
quelle