Ich brauche eine CFG, die andere Saiten als Palindrome erzeugt. Die Lösung wurde bereitgestellt und ist wie folgt: (Einführung in die Theorie der Berechnung - Sipser)
%Vor% Ich bekomme die allgemeine Vorstellung davon, wie diese Grammatik funktioniert. Es erfordert die Einfügung einer Unterzeichenfolge, die entsprechende nicht-gleiche Alphabete auf ihrer Hälfte hat, durch die Produktion S -> aTb | bTa , wodurch sichergestellt wird, dass niemals ein Palindrom erzeugt werden kann.
Ich werde die Semantik der ersten zwei Produktionen aufschreiben, wie ich es verstanden habe,
S erzeugt Zeichenketten, die nicht palindrome sein können, weil ihre ersten und letzten Alphabete nicht gleich sind R besteht aus mindestens einem S als Unterzeichenfolge, um sicherzustellen, dass es sich niemals um ein Palindrom handelt. Ich verstehe die Semantik der dritten Produktion nicht vollständig, d. h.
%Vor%So wie ich es sehe, kann T eine beliebige Kombination von a und b erzeugen, d. h. {a, b} *. Warum konnte es nicht wie
sein? %Vor%Sind die beiden nicht gleichwertig? Da das spätere intuitiver ist, warum wird es nicht verwendet?
Die Konstruktion des Buches, das ich glaube, zeigt eine gewisse Symmetrie zum besseren Lesen.
Es bedeutet, dass es zuerst alles konstruiert, T. Dann gibt es eine Hülle S, so dass es nicht länger ein Palindrom S wird, und dann baut alles darauf.
Letzteres scheint intuitiv zu sein. Wenn Sie jedoch an die Definition oder Konstruktion von Palindrom denken, könnten Sie verstehen, warum das Schreiben auf diese Weise sinnvoll ist.
Wenn Sie ein Palindrom haben, würden Sie so etwas konstruieren
T - & gt; aTa | bTb | a | b | Epsilon
Und wenn wir die Konstruktion verletzen wollen, müssen wir nur sicherstellen, dass es eine Ebene gibt, die so aussieht (ich verwende T als eine Ebene und S als etwas nach T).
S - & gt; aTb
Und andere Ebenen sind uns generell egal
S - & gt; aTa | aTb | bTa | bTb
Also das bildet die innere Schicht (T) und äußere Schicht (R) und die Schicht, die die Konstruktion von Palindrom (S) verletzt. Sogar Gedanke T scheint überflüssig zu sein, aber es bildet die ähnliche Konstruktion wie R und drückt so die Absicht der Konstruktion aus.
Die Definition von T in dieser Grammatik erscheint tatsächlich als unnötige Komplikation. T kann eine beliebige Zeichenfolge von a s und b s generieren, so dass die einfachere Definition genauso gut gewesen wäre.
Ich kann nur vermuten, dass die Produktionen so gegeben werden, wie sie sind, wegen der Wurstfabrik-Art, ein Buch zu schreiben.
ORIGINELLE FALSCHE ANTWORT:
Sie sind nicht gleichwertig, weil X selbst nicht <epsilon> sein kann und T keine Kombination von a und b ist. T kann nur zu einem Palindrom erweitert werden (einschließlich des leeren Palindroms, eines einzelnen Zeichens oder eines Palindroms mit einem ungepaarten zentralen Charakter).
Wenn X leer sein könnte, könnte T auf alles erweitern, aber nicht.
HINWEIS
Diese Antwort basiert auf der Annahme, dass die Absicht des Autors für die Produktion T -> XTX ist, dass die zwei identischen Nicht-Terminals in der Ersetzung identische Zeichenketten darstellen müssen. Da ich den Text nicht zu sehen habe, weiß ich nicht, ob diese Annahme begründet ist, außer dass sie von der Frage selbst motiviert ist. Diese Annahme könnte ein Fehler des Autors sein, wenn dies an anderer Stelle nicht der Fall ist. Ich denke, dass diese Anforderung im Allgemeinen nicht für kontextfreie Grammer gilt.
Die richtigen Produktionen wären:
%Vor%Der beste Weg, um sicherzustellen, dass Sie eine Grammatik haben, die nur Nicht-Palindrome erzeugt, ist die folgende: Definieren:
Beobachter, dass nicht-Pal = {a, b} * - Pal
Die Grammatik für Pal ist wie folgt:
Die Grammatik für {a, b} * kann wie folgt geschrieben werden:
Um nun die Grammatik von Nicht-Pal zu konstruieren, beachten Sie Folgendes:
Kombiniert man all diese Informationen, wäre die Grammatik für Nicht-Pal:
Ich hoffe, dies verdeutlicht die Dinge
Ich fand diese Definition eines Nicht-Palindroms ziemlich intuitiv. Ich nehme an, dass der Autor begann mit einer Definition für ein Palindrom
%Vor%und nun gefragt, wie diese Definition "ruiniert" werden kann.
Das heißt, er entfaltete die Definition dreimal, tauschte ein aRa | bRb by aRb | bRa und generalisierte die restlichen Produktionen auf (a|b)R(a|b) .
Jedes Non Palindrome kann entlang der Mitte geteilt werden, so dass x (k)! = x (k + n)
n = halbe Länge x (i) = Zeichen an der i-ten Position
Eine einfache Lösung wäre
%Vor%Es kann alle Nicht-Palindrome erzeugen
Tags und Links context-free-grammar computation-theory