Eine mit dem Zusammenhang empfindliche Grammatik (CSG) ist eine formelle Grammatik, in der die linken Seiten und Rechten irgendwelcher Produktionsregeln durch einen Zusammenhang von End- und Nichtendsymbolen umgeben werden können. Mit dem Zusammenhang empfindliche Grammatiken sind allgemeiner als Grammatiken ohne Zusammenhänge, aber noch regelmäßig genug, um durch einen geradlinigen begrenzten Automaten grammatisch analysiert zu werden.

Das Konzept der mit dem Zusammenhang empfindlichen Grammatik wurde von Noam Chomsky in den 1950er Jahren als eine Weise eingeführt, die Syntax der natürlichen Sprache zu beschreiben, wo es tatsächlich häufig der Fall ist, dass ein Wort kann oder in einem bestimmten Platz abhängig von Zusammenhang nicht passend sein kann. Eine formelle Sprache, die durch eine mit dem Zusammenhang empfindliche Grammatik beschrieben werden kann, wird eine mit dem Zusammenhang empfindliche Sprache genannt.

Formelle Definition

Eine formelle Grammatik G = (N, Σ, P, S) (ist das dasselbe als G = (V, T, P, S) gerade, dass das Nichtterminal V (ariable) durch N und T (erminal) ersetzt wird, wird durch Σ ersetzt), ist mit dem Zusammenhang empfindlich, wenn alle Regeln in P von der Form sind

: αAβ  γ\

wo Ein  N (d. h., A ein einzelnes Nichtterminal ist), α,β  (N U Σ)* (d. h., α und β Reihen von Nichtterminals und Terminals sind) und γ  (N U Σ) (d. h., ist γ eine nichtleere Reihe von Nichtterminals und Terminals).

Einige Definitionen fügen auch hinzu, dass für jede Produktionsregel der Form u  v einer mit dem Zusammenhang empfindlichen Grammatik es dass |u |  | v | wahr sein soll. Hier zeigen |u | und |v | die Länge der Schnuren beziehungsweise an.

Außerdem, eine Regel der Form

: S  hat λ S zur Verfügung gestellt erscheint auf der richtigen Seite keiner Regel

wo λ die leere Schnur vertritt, wird erlaubt. Die Hinzufügung der leeren Schnur erlaubt die Behauptung, dass der Zusammenhang empfindliche Sprachen sind eine richtige Obermenge des Zusammenhangs freie Sprachen, anstatt die schwächere Erklärung abgeben zu müssen, dass der ganze Zusammenhang freie Grammatiken ohne  λ Produktion auch Zusammenhang empfindliche Grammatiken ist.

Der mit dem Zusammenhang empfindliche Name wird durch den α und die β erklärt, die den Zusammenhang von A bilden und bestimmen, ob A durch γ ersetzt werden kann oder nicht. Das ist von einer Grammatik ohne Zusammenhänge verschieden, wo der Zusammenhang eines Nichtterminals nicht in Betracht gezogen wird. (Tatsächlich ist jede Produktion eines Zusammenhangs freie Grammatik ist der Form V  w, wo V ein einzelnes Nichtendsymbol und w ist, eine Reihe von Terminals, und/oder Nichtterminals (w kann leer sein)).

Wenn die Möglichkeit, die leere Schnur zu einer Sprache hinzuzufügen, zu den Schnuren hinzugefügt wird, die durch die Nichtzusammenziehen-Grammatiken anerkannt sind (der die leere Schnur nie einschließen kann) dann, sind die Sprachen in diesen zwei Definitionen identisch.

Beispiele

• Diese Grammatik erzeugt das kanonische nicht Zusammenhang freie Sprache:

Die Generationskette für aaa bbb ccc ist:

:::::::::::::

Mehr komplizierte Grammatiken können verwendet werden, um, und andere Sprachen mit noch mehr Briefen grammatisch zu analysieren.

• Die folgende Grammatik erzeugt den nicht Zusammenhang freie Kopie-Sprache:

Die Generationskette für abab ist:

::::::::

Normale Formen

Jede mit dem Zusammenhang empfindliche Grammatik, die die leere Schnur nicht erzeugt, kann in eine gleichwertige in Kuroda normale Form umgestaltet werden. "Gleichwertig" hier bedeutet, dass die zwei Grammatiken dieselbe Sprache erzeugen. Die normale Form wird nicht im Allgemeinen mit dem Zusammenhang empfindlich sein, aber wird eine Nichtzusammenziehen-Grammatik sein.

Rechenbetonte Eigenschaften und Gebrauch

Das Entscheidungsproblem, das fragt, ob eine bestimmte Schnur s der Sprache einer bestimmten mit dem Zusammenhang empfindlichen Grammatik G gehört, ist PSPACE-abgeschlossen. Es gibt sogar einige mit dem Zusammenhang empfindliche Grammatiken, deren festes Grammatik-Anerkennungsproblem PSPACE-abgeschlossen ist.

Das Leere-Problem für mit dem Zusammenhang empfindliche Grammatiken (gegeben eine mit dem Zusammenhang empfindliche Grammatik G, ist?) ist unentscheidbar.

Es ist gezeigt worden, dass fast alle natürlichen Sprachen im Allgemeinen durch mit dem Zusammenhang empfindliche Grammatiken charakterisiert werden können, aber die ganze Klasse von CSG'S scheint, viel größer zu sein, als natürliche Sprachen. Schlechter noch da ist das oben erwähnte Entscheidungsproblem für den CSG'S PSPACE-abgeschlossen, der sie völlig unausführbar für den praktischen Gebrauch macht, weil ein polynomisch-maliger Algorithmus für ein PSPACE-ganzes Problem P=NP einbeziehen würde. Die andauernde Forschung über die linguistische Datenverarbeitung hat sich darauf konzentriert, andere Klassen von Sprachen zu formulieren, die "mild mit dem Zusammenhang empfindlich sind", wessen Entscheidungsprobleme, wie baumangrenzende Grammatiken, combinatory categorial Grammatiken, verbundene Sprachen ohne Zusammenhänge und geradlinige Neuschreiben-Systeme ohne Zusammenhänge ausführbar sind. Die Sprachen, die durch diese Formalismen richtig erzeugt sind, liegen zwischen den mit dem Zusammenhang empfindlichen Sprachen ohne Zusammenhänge.

Siehe auch

• Hierarchie von Chomsky
• Einführung in Sprachen und die Theorie der Berechnung durch John C. Martin McGraw Hill 1996 (2. Ausgabe)

Links

• Earley, der für mit dem Zusammenhang empfindliche Grammatiken grammatisch analysiert