Kommunizierendes Grammatik-System

Grundidee kommunizierender Grammatik-Systeme

Kommunizierende Grammatik-Systeme bestehen aus mehreren formalen Grammatiken, die miteinander kommunizieren können. Die konkrete Kommunikationsart hängt vom jeweiligen System ab. Durch das Zusammenwirken kann die generative Mächtigkeit, also die Fähigkeit, Sprachen zu erzeugen, über die Möglichkeiten der einzelnen Grammatiken hinausgehen.

Solche Systeme gelten als komplex: Die Fähigkeiten des Gesamtsystems lassen sich nicht unmittelbar allein aus den Fähigkeiten seiner Einzelkomponenten ableiten. Zwei Beispiele sind verteilt kooperierende Grammatik-Systeme (cooperating distributed Grammar Systems, CDGS) und parallel kommunizierende Grammatik-Systeme (parallel communicating Grammar Systems, PCGS).

Zusammenarbeit im Tafel- und Klassenraum-Modell

Das Tafel-Modell beschreibt die Zusammenarbeit in verteilt kooperierenden Grammatik-Systemen. Das benötigte Wissen ist auf unabhängige Agenten verteilt. Alle Agenten arbeiten gleichzeitig an einer gemeinsamen Datenbank, der „Tafel“, um ein Problem zu lösen. Auf Grammatiken übertragen bedeutet dies, dass die beteiligten Grammatiken an einer gemeinsamen Ableitung arbeiten. Die Kontrolle der Agenten ist deshalb ein wichtiger Bestandteil solcher Systeme.

Das Klassenraum-Modell modelliert parallel kommunizierende Grammatik-Systeme. Jeder Agent besitzt ein eigenes Notizbuch mit der Beschreibung eines Teilproblems und darf nur auf seiner eigenen Kopie arbeiten. Ein eindeutig bestimmter Agent darf allein auf die Tafel schreiben; die Agenten können über ihre Notizbücher miteinander kommunizieren. Jede Grammatik erzeugt eine eigene Ableitungsform, doch nur die von der Hauptgrammatik erzeugte Ableitung löst das Problem. Wie intensiv die Grammatiken kommunizieren, hängt vom jeweiligen System ab.

Steigerung der generativen Mächtigkeit

Die Kommunikation steigert die generative Mächtigkeit abhängig von der Mächtigkeit der einzelnen Komponenten.

Schon ein System aus drei parallel kommunizierenden regulären Grammatiken, also Typ-3-Grammatiken der Chomsky-Hierarchie, kann kontextsensitive Sprachen erzeugen. Für die generative Mächtigkeit solcher Systeme ist eine unendliche Hierarchie bewiesen. Ein Pumping-Lemma besagt, dass jede zusätzliche reguläre Grammatik in einem Grammatik-System neue Sprachen ermöglicht, die das Ausgangssystem noch nicht erzeugen konnte.

Kontextsensitive Grammatiken besitzen eine so hohe generative Mächtigkeit, dass bei Grammatik-Systemen – je nach Kommunikationsart – bereits zwei bis drei Komponenten ausreichen, um alle rekursiv aufzählbaren Sprachen zu generieren.