Kommunizierendes Grammatik-System

Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen und beteilige dich an der Diskussion! (+)

Kommunizierende Grammatik-Systeme bestehen aus mehreren formalen Grammatiken, die über eine Möglichkeit verfügen, miteinander zu kommunizieren. Die Art der Kommunikation ist vom jeweiligen System abhängig und kann die generative Mächtigkeit der einzelnen Grammatiken erweitern.

Kommunizierende Grammatik-Systeme können somit als komplexe Systeme betrachtet werden, da durch die Interaktion mehrerer Einzelkomponenten die Fähigkeiten des Systems nicht sofort aus den Fähigkeiten der einzelnen Komponenten ersichtlich sind.

Verteilt kooperierende Grammatik-Systeme (cooperating distributed Grammar Systems / CDGS) und parallel kommunizierende Grammatik-Systeme (parallel communicating Grammar Systems / PCGS) sind Beispiele für diese Art von Systemen.

Modelle

Tafel-Modell

Ein Modell für die Zusammenarbeit von verteilt kooperierenden Grammatik-Systemen ist das sogenannte Tafel-Modell. Hierbei wird das zur Bearbeitung benötigte Wissen auf unabhängige Agenten verteilt, die alle gemeinsam an einer Tafel versuchen, ein Problem zu lösen. Hierbei versuchen alle Agenten gleichzeitig, das Problem zu lösen und arbeiten auf der gleichen Datenbank, der Tafel. Auf Grammatiken übertragen arbeiten die teilnehmenden Grammatiken an einer gemeinsamen Ableitung.

Deshalb ist die Kontrolle der Agenten ein wichtiger Bestandteil dieser Grammatik-Systeme.

Klassenraum-Modell

Das Klassenraum-Modell ist eine Modellierung von parallel kommunizierenden Grammatik-Systemen. Hierbei erhält jeder Agent sein eigenes Notizbuch, das die Beschreibung eines Teilproblems enthält. Jeder Agent darf nur auf seiner Kopie arbeiten. Es gibt einen eindeutig bestimmten Agenten, der alleine auf die Tafel schreiben kann. Die Agenten dürfen untereinander über ihre Notizbücher kommunizeren.

Jede Grammatik erzeugt somit ihre eigene Ableitungsform, aber nur die von der Hauptgrammatik produzierte Ableitung löst das Problem. Wie weit die einzelnen Grammatiken miteinander kommunizieren ist vom jeweiligen System abhängig.

Generative Mächtigkeit

Die generative Mächtigkeit wird durch die Kommunikation in Abhängigkeit von der generativen Mächtigkeit der einzelnen Komponenten gesteigert.

PCGS aus Typ-3-Grammatiken

Bereits Systeme aus drei parallel kommunizierenden regulären Grammatiken (Typ-3-Grammatiken nach der Chomsky-Hierarchie) können kontextsensitive Sprachen erzeugen.

Eine unendliche Hierarchie für die generative Mächtigkeit dieser Systeme wurde bewiesen. Es existiert ein Pumping-Lemma mit der Aussage, dass jede zusätzliche reguläre Grammatik in einem Grammatik-System zu neuen Sprachen führt, die das Ausgangssystem noch nicht generieren konnte.

PCGS von Typ 1

Die generative Mächtigkeit einer kontextsensitive Grammatik ist so stark, dass mit Hilfe von Grammatik-Systemen je nach Kommunikationsart bereits zwei bis drei Komponenten ausreichen, um alle rekursiv aufzählbaren Sprachen zu generieren.

Literatur

• Herbert A. Simon: The Sciences of the Artificial. 2nd Edition. MIT Press, Cambridge, MA 1982, ISBN 0-262-69073-X.
• Erzsébet Csuhaj-Varjú, J. Dassow, J. Kelemen, Gh. Paun: Grammar Systems. A grammatical Approach to Distribution and Cooperation. Gordon and Breach, Yverdon u. a. 1994, ISBN 2-88124-957-4, (Topics in computer mathematics 5).