So generieren Sie eine kontextsensitive Grammatik für www

7

Ich versuche, meine bevorstehende Prüfung zu lösen, und habe keine Ahnung, wie ich die Grammatik für kontextsensitive Sprachen generieren soll, zum Beispiel, wie ich mit dieser Art von Frage vorgehen soll.

Geben Sie eine kontextsensitive (nicht nur längenerhöhende) Grammatik für an {www:w{a,b}}.

Ideen oder Ansätze zum Umgang mit solchen Fragen werden sehr geschätzt.

User_1234
quelle
4
Idee: Jedes Mal, wenn Sie ein "a" generieren, generieren Sie auch "a" und "a" (dasselbe gilt für "b"). Jetzt kann ein '' mit einem nicht grundierten Buchstaben rechts davon wechseln (aber nicht mit einem grundierten oder doppelt grundierten Buchstaben). Am Ende die Primzahlen loswerden.
Ran G.
1
Hinweis: „www“ ist nicht kontextfrei so dass Sie haben die Verwendung der zusätzlichen Einrichtungen kontextsensitiven Grammatiken Sie geben zu machen. Ein häufiges Thema ist das Umschalten von Nicht-Terminals, um sie effektiv im Satz zu verschieben. Daher ist es einfach, einen TM-Kopf mit der Grammatik zu simulieren. Wie würden Sie "www" algorithmisch entscheiden?
Raphael

Antworten:

5

Intuitiv möchten Sie drei Zwischensymbole gleichzeitig generieren und den Symbolen erlauben, sich selbst zu sortieren. LassenSsei das Startsymbol. Die Generierungsregeln sind:

SSA1A2A3
SSB1B2B3
Die Sortierregeln lauten wie folgt: Für Symbole Xi,Yi{A1,A2,A3,B1,B2,B3} so dass j<i füge die Regel hinzu:
XiYjYjXi
Am Ende müssen wir die Zwischensymbole in Terminalsymbole verwandeln. Verwandeln Sie das Startsymbol in ein anderes SymbolS1 die Erzeugungsphase zu beenden.
SS1
Schieben Sie durch die Zeichenfolge, um Symbole auf dem Weg in Terminalsymbole umzuwandeln, und erhöhen Sie den Index, wenn Sie mit einem Wort fertig sind . Für alle fügen Sie die Regeln hinzu: Der Index von stellt sicher, dass die Symbole in der richtigen Reihenfolge konvertiert werden, da der Index nicht verringert werden kann. Am Ende entfernen Sie . S1wi{1,2,3}
SiAiaSi|aSi+1
SiBibSi|bSi+1
SS3
S3ε
jnalanko
quelle
2
Obwohl Ihre Grammatik nahe kommt, ist sie aufgrund von Regeln wie "weder User_1234 angefordert) kontextsensitiv (nach dem User_1234 gefragt hat).ABBA"noch monoton wegen S3ϵ.
lukas.coenig
@ lukas.coenig Die Epsilon-Regel ist zwar nicht erlaubt (sollte leicht zu beheben sein), aber ansonsten ist die Grammatik in Kuroda-Normalform . Nicht jede Definition von CSGs gibt es zu, aber es ist bekanntlich eine äquivalente Definition. Wenn das OP (oder ein Leser) eine andere Definition verwenden muss, kann es Konstruktionen verwenden, die aus Äquivalenznachweisen der Definitionen stammen, und diese (mechanisch) auf diese Lösung anwenden.
Raphael
1
@ Raphael. Danke, aber ich denke nicht, dass es so einfach ist. Betrachten Sie das Wortaaazum Beispiel. Um dieses Wort zu erhalten, müssen Sie mit beginnenSSA1A2A3. Die Länge dieser sententialen Form beträgt 4, während die Länge vonaaaist 3, also müssten Sie irgendwo auf der Straße die Länge der sententialen Form verringern. Dies ist jedoch in einer kontextsensitiven Grammatik nicht zulässig, da sie nicht abnimmt, dh für jede Produktionxymuss man haben xy. Wenn ich mich nicht irre, bedeutet dies, dass die Lösung von jnalanko völlig falsch ist. Ich kann jedoch keine richtige Lösung finden ...
Barbara
1
@ Barbara Es scheint, wir verstehen uns falsch. Ich wollte die ganze Grammatik umgestalten; Sie würden mit ; obere Indizes würde "rechts von " ersetzen . Abstrakt kann jeder "Overhead" konstanter Größe in spezielle Symbole gefaltet werden. (Ich denke.)A10A2A3iSi
Raphael
1
@ Barbara An dieser Stelle denke ich, dass Sie eine neue Frage öffnen sollten. Wenn der Weg von hier zu dem, was Sie brauchen, nicht so einfach ist, wie ich dachte, ist eine Diskussion in den Kommentaren nicht der richtige Weg, um dies zu klären.
Raphael
2

Die Antwort für Ihr spezifisches Beispiel ist da, aber die allgemeine Frage bleibt.

In sehr vielen Jahren, sowohl in der theoretischen als auch in der angewandten Informatik, erinnere ich mich nicht daran, eine CS-Grammatik als solche schreiben zu müssen.

Wenn ich jedoch einen Rat geben darf, sollte dies überhaupt nicht als Erstellung einer CF-Grammatik angesehen werden, wenn Sie die Regeln erfinden müssen, um alles in Ordnung zu bringen und genau richtig zu koordinieren, wie es erstellt wird.

CS-Grammatiken sind viel algorithmischer, und Sie können eine Turing-Maschine (die im endlichen Raum arbeitet, proportional zur Eingabegröße, was Linear Bounded Automaton - LBA bedeutet) ziemlich genau nachahmen, um die Dinge nach Bedarf zu bewegen. Es ist also viel mehr eine Programmierübung.

Sie können so ziemlich die ersten Zutaten generieren, um eines der Wörter in der Sprache zu erstellen, und sie dann algorithmisch verschieben. Sie können spezielle Symbole (möglicherweise in verschiedenen Geschmacksrichtungen, die dem endlichen Zustand entsprechen) verwenden, um als Köpfe zu fungieren, die Sie mit geeigneten Regeln bewegen, und um zu überprüfen, was zu tun ist. Und so weiter.

Eine gute Lektüre kann darin bestehen, den Beweis der Gleichwertigkeit zwischen CSG-Sprachen und LBA-Sprachen, dh den CS-Sprachen, zu prüfen.

Denken Sie daran, dass fast alle Algorithmen, mit denen wir arbeiten, von einem LBA ausgeführt werden können und daher einer CSG-definierbaren Sprache entsprechen. Das sollte Ihnen eine Vorstellung von der verfügbaren algorithmischen Leistung geben.

Aber ein bisschen Fantasie hilft bei eleganten Lösungen, wie in dem Beispiel, das Sie gegeben haben.

babou
quelle
Wie kann man für die in der Frage von User_1234 angegebene Sprache einen LBA dafür entwerfen? Ich habe nur Erfahrung mit dem Entwerfen von Turingmaschinen für Sprachen mit Trennzeichen. Zum Beispiel: , was die Dinge einfacher zu machen scheint. {w#w#w:w{a,b}}
David Smith
@DavidSmith Für gibt es eine einfache spezifische Lösung, die im ersten Ran G-Kommentar und mit Details in der vorherigen Lösung angegeben ist. Dies unterscheidet sich ein wenig von TM, die normalerweise als Akzeptoren (Erkenner) konstruiert sind, während Sie hier einen Konstruktor wünschen. Eine andere Möglichkeit besteht darin, eine Zeichenfolge zu generieren , dann 2 Symbole auf einer Seite hinzuzufügen und dann jedes Symbol durch eine Kopie der Zeichenfolge ersetzen . Dies ist komplexer, funktioniert jedoch für eine beliebige Anzahl von Kopien von , indem nur die Anzahl der Symbole erhöht wird . wwww##ww#
Babou
@DavidSmith Ein LBA ist ein Akzeptor, den Sie so ziemlich wie ein TM "programmieren". In diesem Fall können Sie, wenn Sie und es erkennen möchten, einfach eine erste Berechnung durchführen, bei der die Symbole (auf viele Arten) gezählt werden, um die beiden an der richtigen Stelle zu platzieren. Alternativ können Sie sich auf Nichtdeterminismus verlassen und die beiden an zufälligen Stellen in der Eingabezeichenfolge platzieren. Eine Auswahl von ihnen ist gut, wenn die Zeichenfolge in der Sprache ist. www##
Babou
1

Dies ist nur eine zusätzliche Antwort, die als allgemeine Lösung angesehen werden kann. CSLs, kontextsensitive Sprachen, werden durch LBAs, linear begrenzte Automaten, modelliert . Ein LBA ist eine Turing-Maschine, die ein Arbeitsband annehmen oder ablehnen kann, das nicht größer als das Konstante mal die Größe des Eingabebandes ist. Wenn Sie also ein Computerprogramm finden können, das die Eingabe in einem konstanten Raum verarbeiten kann, dann ist es eine CSL. Idee: Ein Programm, das für dieses Problem geeignet ist, würde so etwas wie Permutationen in konstantem Raum aufzählen.

vzn
quelle