In der Computerlinguistik, der Ausdruck mild kontextsensitive Grammatikformalismen bezieht sich auf mehrere Grammatikformalismen, die mit dem Ziel entwickelt wurden, um eine angemessene Beschreibung der syntaktischen Struktur der natürlichen Sprache zu schaffen.

Jeder mild kontextsensitive Grammatik Formalismus definiert eine Klasse von mild kontextsensitive Grammatiken, und damit auch eine Klasse von mild kontextsensitive Sprachen.

Hintergrund

Bis 1985 waren mehrere Forscher in der Beschreibung und mathematischen Linguistik Beweise gegen die Hypothese, dass die syntaktische Struktur der natürlichen Sprache ausreichend durch kontextfreien Grammatiken beschrieben wird. Zur gleichen Zeit, den Schritt auf die nächste Stufe der Chomsky-Hierarchie, um kontextsensitive Grammatiken, erschienen sowohl unnötig und unerwünscht. In einem Versuch, die genaue formale Macht für die angemessene Beschreibung der natürlichen Sprachsyntax erforderlich festzulegen, dadurch gekennzeichnet, Aravind Joshi 'Grammatiken, die nur geringfügig stärker als kontextfreien Grammatiken sind'. Er nannte diese Grammatiken mild kontextsensitive Grammatiken und die zugehörigen Sprachen mild kontextsensitive Sprachen.

Joshi Charakterisierung von mild kontextsensitive Grammatiken kam auf seine Arbeit an Bäumen angrenzenden Grammatik vorgespannt ist. Doch zusammen mit seinen Studenten Vijay Shanker und David Weir, Joshi entdeckte bald, dass TAGs äquivalent sind, in Bezug auf den erzeugten String Sprache, der unabhängig eingeführten Kopf Grammatik. Dies wurde durch zwei ähnliche Äquivalenz Ergebnisse folgen, für lineare indexiert Grammatik und kombi Kategorialgrammatik, was zeigte, dass der Begriff der milde Kontextsensitivität ist ein sehr allgemein gehalten und nicht auf eine bestimmte Formalismus gebunden.

Die TAG-Äquivalent Formalismen wurden durch die Einführung der linearen kontextfreien Ersetzungssysteme verallgemeinert. Diese Grammatiken definieren eine unendliche Hierarchie von String Sprachen in zwischen der kontextfreien und der kontextsensitiven Sprachen, mit den durch die TAG-Äquivalent Formalismen am unteren Ende der Hierarchie erzeugt Sprachen. Unabhängig und fast gleichzeitig LCFRS, Hiroyuki Seki et al. vorgeschlagen, die im wesentlichen identisch Formalismus mehrerer kontextfreien Grammatik. LCFRS / MCFG wird manchmal als die allgemeinste Formalismus zum Spezifizieren mild kontextsensitiven Grammatiken betrachtet. Allerdings haben einige Autoren bemerken, dass einige der charakteristischen Eigenschaften der TAG-Äquivalent Formalismen nicht durch LCFRS / MCFG, und dass es Sprachen, die die charakteristischen Eigenschaften leicht Kontextsensitivität aufweisen, jedoch nicht durch LCFRS / MCFG erzeugt bewahrt.

In den letzten Jahren haben gesehen, erhöhte Interesse an der eingeschränkten Klasse von gut verschachtelten linearen kontextfreien Ersetzungssysteme / mehrere kontextfreien Grammatiken, die eine Klasse von Grammatiken, die ordnungsgemäß schließt die TAG-Äquivalent Formalismen, aber richtig in die uneingeschränkte LCFRS enthalten definieren / MCFG Hierarchie.

Charakterisierung

Trotz einer beträchtlichen Menge an Arbeiten zu diesem Thema gibt es keine allgemein anerkannte formale Definition der milde Kontextsensitivität.

Entsprechend der ursprünglichen Charakterisierung durch Joshi, einer Klasse von mild kontextsensitiven Grammatiken sollten die folgenden Eigenschaften haben:

• begrenzte Querserien Abhängigkeiten
• stetiges Wachstum
• Polynom-Parsing

Zusätzlich zu diesen, ist es selbstverständlich, dass jede Klasse von mild kontextsensitive Grammatiken sollten in der Lage, alle kontextfreien Sprachen generieren.

Joshi Charakterisierung ist nicht eine formale Definition. Er stellt fest:

Andere Autoren haben alternative Charakterisierungen milden Kontextsensitivität, von denen einige in Form von formalen Definitionen vorgeschlagen. Zum Beispiel Laura Kallmeyer nimmt die Perspektive, dass milde Kontextsensitivität sollte als Eigenschaft der Klassen von Sprachen, anstatt, wie in Joshi Charakterisierung, Klassen von Grammatiken definiert werden. Eine solche Sprache-basierte Definition führt zu einer anderen Vorstellung von dem Begriff als Joshi.

Cross-Serien Abhängigkeiten

Der Begriff Cross-Serien Abhängigkeiten bezieht sich auf bestimmte charakteristische Wortbestellverhalten, insbesondere auf die in Nebensätzen in niederländischen und schweizerischen deutschen beobachtet Verb-Argument Mustern. Das sind genau die Muster, die verwendet werden können, um gegen den Rahmen-Mahlgrad von natürlicher Sprache streiten; erfordern somit mild kontextsensitive Grammatiken für die grenzüberSerien Abhängigkeiten modellieren bedeutet, dass diese Grammatiken müssen stärker als kontextfreien Grammatiken sein.

Kallmeyer kennzeichnet die Fähigkeit, Querserien Abhängigkeiten mit der Fähigkeit, um die Kopie zu erzeugen Sprache zu modellieren

und ihre Verallgemeinerungen, um zwei oder mehr Kopien von W, bis zu einer bestimmten Grenze. Diese Sprachen sind nicht kontextfrei, die mit Hilfe des Pumping-Lemma gezeigt werden kann.

Stetiges Wachstum

Eine formale Sprache, eine konstante Wachstums wenn jede Zeichenfolge in der Sprache länger ist als die nächst kürzere Saiten um höchstens eine Konstante ist. Sprachen, die diese Eigentumsrechte verletzen, werden oft als jenseits der menschlichen Fähigkeit zu sein, obwohl einige Autoren haben argumentiert, dass bestimmte Phänomene in natürlicher Sprache zu tun zeigen ein Wachstum, das nicht durch eine Konstante beschränkt werden kann.

Die meisten mild kontextsensitive Grammatikformalismen tatsächlich erfüllen eine stärkere Eigenschaft als konstantes Wachstum genannt semilinearity. Eine Sprache ist semilineare, wenn sein Bild unter dem Parikh-Mapping ist eine reguläre Sprache. Alle semilineare Sprachen sind von ständigem Wachstum, aber nicht jede Sprache mit stetigem Wachstum ist semilineare.

Polynom-Parsing

Ein Grammatikformalismus wird gesagt, Polynom-Parsing, wenn seine Mitgliedschaft Problem kann in deterministischer Polynomialzeit gelöst werden. Dies ist das Problem, zu entscheiden, da eine Grammatik G in dem Formalismus und einem Wort w geschrieben, ob w durch G erzeugt - das heißt, ob w grammatische 'gemäß G. Es Komplexität dieses Problems ist im Hinblick auf gemessene der Gesamtgröße G und w.

Unter dem Blick auf milde Kontextsensitivität als Eigenschaft der Klassen von Sprachen, bezieht Polynom Parsen der Sprache Mitgliedschaft Problem. Das ist das Problem, um zu entscheiden, für einen festgelegten Sprache L, ob eine gegebene Zeichenkette w gehört L. Die Zeit Komplexität dieses Problems ist im Hinblick auf die Länge von w, gemessen; Sie ignoriert die Frage, wie L angegeben.

Beachten Sie, dass beide Auffassungen von Polynom-Parsing sind Idealisierungen in dem Sinne, dass für praktische Anwendungen eine interessierte nicht nur in den Ja / Nein-Frage, ob ein Satz ist grammatischen, sondern auch in der syntaktischen Struktur, die die Grammatik weist dem Satz ist.

Formalismen

Im Laufe der Jahre ist eine große Anzahl von Grammatikformalismen eingeführt worden, einige oder alle der charakteristischen Eigenschaften her von Joshi setzen befriedigen. Mehrere von ihnen haben alternative, Automaten-basierten Kennzeichnungen, die nicht in diesem Artikel behandelt werden; zum Beispiel können die von einem mit Bäumen angrenzenden Grammatik generiert Sprachen von Embedded-Kellerautomaten charakterisiert werden.

Formalismen entspricht TAG

• Baum angrenzenden Grammatik
• Leiter Grammatik
• Linear indizierten Grammatik
• Kombinatorische Kategorialgrammatik
• Wohl verschachtelten LCFRS / MCFG der Fan-Out-2

Formalismen entspricht allgemeinen LCFRS / MCFG

• Linear kontextfreien Ersetzungssysteme
• Mehrere kontextfreien Grammatiken
• Mehrbaum angrenzenden Grammatiken
• Minimalistische Grammatiken
• Einfach, positiven Bereich Verkettung Grammatiken

Formalismen entspricht gut verschachtelten LCFRS / MCFG

• Nicht-Duplizierung Makro Grammatiken
• Gekoppelt kontextfreien Grammatiken
• Wohl verschachtelten linearen kontextfreien Ersetzungssysteme
• Wohl verschachtelten mehrere kontextfreien Grammatiken

Die Beziehungen zwischen den Formalismen

Linear kontextfreien Ersetzungssysteme / mehrere kontextfreien Grammatiken bilden eine zweidimensionale Hierarchie von Zeugungskraft in Bezug auf zwei Grammatik spezifischen Parametern aufgerufen Fan-Out und Rang. Genauer gesagt, die von LCFRS / MCFG erzeugt mit Fan-Out-f ≥ 1 und Rang r Sprachen ≥ 3 ordnungsgemäß in der Klasse der Sprachen, die von LCFRS / MCFG mit Rang r + 1 und Fan-out-f erzeugt enthalten, sowie die Klasse der Sprachen, die von LCFRS / MCFG mit Rang r und Fan-out-f + 1. In Gegenwart von gut nestedness erzeugt, bricht diese Hierarchie auf eine eindimensionale Hierarchie in Bezug auf Fan-out; Das ist, weil jeder gut verschachtelten LCFRS / MCFG kann in eine äquivalente gut verschachtelten LCFRS / MCFG mit der gleichen Fan-Out und Rang 2. Im LCFRS / MCFG Hierarchie, die kontextfreien Sprachen können von den Grammatiken charakterisiert werden verwandelt werden mit Fan-Out-1; für diese Fan-out gibt es keinen Unterschied zwischen der allgemeinen und gut verschachtelt Grammatiken. Die TAG-Äquivalent Formalismen können auch verschachtelte LCFRS / MCFG der Fan-Out-2 bezeichnet werden.