Bereiche Verkettung Grammatik

Bereiche Verkettung Grammatik (RCG) ist ein von Pierre Boullier entwickelter Grammatikformalismus [1] 1998 als Versuch, eine Reihe von Phänomenen der natürlichen Sprache zu charakterisieren, wie z. leicht kontextsensitive Sprachen.[2]

Aus theoretischer Sicht, jede Sprache, die analysiert werden kann Polynomzeit gehört zur Teilmenge von RCG, die als positive Reichweite von Verkettungsgrammatiken bezeichnet werden, und gegenseitig.[4]

Obwohl als Variante bei Groenink's gedacht Wörtliche Bewegungsgrammatiken (LMGs), RCGs behandeln den grammatikalischen Prozess eher als Beweis als als Produktion. Während LMGs von einem Startprädikat eine terminale Zeichenfolge erzeugen, zielen RCGs darauf ab, ein Startprädikat (das eine terminale Zeichenfolge Prädikate) auf die leere Zeichenfolge reduzieren, was einen Beweis für die terminale Strings -Mitgliedschaft in der Sprache ausmacht.

Beschreibung

Formale Definition

A Übereinstimmungsgrammatik mit positiver Reichweite (PRCG) ist ein Tupel , wo:

  • , und sind disjunkte endliche Sätze von (jeweils) Prädikatnamen, Terminalsymbole und Variablennamen. Jeder Prädikatname hat eine von der Funktion angegebene Arität .
  • Ist der Name des Startprädikats und überprüfen Sie .
  • ist ein endlicher Satz von Klauseln der Form , bei dem die sind Prädikate der Form mit und .

A Verkettungsgrammatik negativer Bereiche (NRCG) ist wie ein PRCG definiert, aber mit der Zugabe, dass einige Prädikate, die auf der rechten Seite einer Klausel auftreten, die Form haben können . Solche Prädikate werden genannt Negative Prädikate.

A Bereiche Verkettung Grammatik ist positiv oder negativ. Obwohl PRCGs technisch gesehen NRCGs sind, werden die Begriffe verwendet, um die Abwesenheit (PRCG) oder das Vorhandensein (NRCG) negativer Prädikate hervorzuheben.

A Angebot in einem Wort ist ein Paar , mit , wo ist die Länge von . Zwei Bereiche und kann mit dem IFF verkettet werden und wir haben dann: .

Für ein Wort , mit , das gepunktete Notation Für Bereiche ist: .

Anerkennung von Saiten

Wie LMGs haben RCG -Klauseln das allgemeine Schema , wo in einem RCG, ist entweder die leere Zeichenfolge oder eine Zeichenfolge von Prädikaten. Die Argumente bestehen aus Zeichenfolgen von terminalen Symbolen und/oder variablen Symbolen, die Muster mit den tatsächlichen Argumentwerten wie in LMG übereinstimmen. Benachbarte Variablen bilden eine Spielfamilie gegen Partitionen, so dass das Argument Mit zwei Variablen entspricht die wörtliche Zeichenfolge Auf drei verschiedene Arten: .

Prädikatbegriffe sind in zwei Formen erhältlich, positiv (die die leere Zeichenfolge für den Erfolg erzeugen) und negativ (die die leere Zeichenfolge für den Fehler erzeugen/wenn der positive Term tut nicht die leere Zeichenfolge erzeugen). Negative Begriffe werden mit positiv .

Die Umschreibungssemantik für RCGs ist ziemlich einfach und identisch mit der entsprechenden Semantik von LMGs. Bei einer Prädikatzeichenfolge , wo die Symbole sind terminale Zeichenfolgen, wenn es eine Regel gibt In der Grammatik, in der die Prädikat -Zeichenfolge übereinstimmt, wird die Prädikat -Zeichenfolge durch ersetzt Ersetzen Sie die übereinstimmenden Variablen in jedem .

Zum Beispiel angegeben die Regel , wo und sind variable Symbole und und sind terminale Symbole, die Prädikatzeichenfolge kann als umgeschrieben werden wie , Weil Streichhölzer Wenn . In ähnlicher Weise, wenn es eine Regel gab , könnte als umgeschrieben wie .

Ein Beweis/Erkennen einer Zeichenfolge wird durchgeführt, indem das zeigt erzeugt die leere Schnur. Bei den einzelnen Umschreibschritten, wenn mehrere alternative Variablenübereinstimmungen möglich sind, wird jeder Umschreiben, der den gesamten Nachfolger zum Erfolg führen kann, berücksichtigt. Wenn es also mindestens eine Möglichkeit gibt, die leere Zeichenfolge aus der Anfangszeichenfolge zu erzeugen Der Beweis wird als Erfolg angesehen, unabhängig davon, wie viele andere Möglichkeiten zu scheitern sind.

Beispiel

RCGs können die nichtlineare Indexsprache erkennen folgendermaßen:

X, y und z variable Symbole sein lassen:



Der Beweis für Abbabbabb ist dann

Oder verwenden Sie die korrektere gepunktete Notation für Bereiche:

Verweise

  1. ^ Boullier, Pierre (Januar 1998). Vorschlag für ein syntaktisches Rückgrat für natürliche Sprachverarbeitung (PDF) (Technischer Bericht). Vol. 3342. Inria Rocquencourt (Frankreich).
  2. ^ Pierre Boullier (1999). "Chinesische Zahlen, Mix-, Krabbeln und Reichweitenverzögerungsgrammatiken" (PDF). Proc. EACCL. S. 53–60. Archiviert von das Original (PDF) am 2003-05-15.
  3. ^ Eberhard Bertsch und Mark-Jan Nederhof (Okt 2001). "Über die Komplexität einiger Erweiterungen des RCG -Parsens" (PDF). Verfahren des siebten internationalen Workshops für Parsing -Technologien (Peking). S. 66–77.
  4. ^ Laura Kallmeyer (2010). Analysen über kontextfreie Grammatiken übergehen. Springer Science & Business Media. p. 37. ISBN 978-3-642-14846-0. Zitieren von Bertsch, Nederhof (2001)[3]