Eine Graph-Grammatik besteht aus einer Menge von Produktionsregeln zur Konstruktion aller gültigen Sätze in einer Graphsprache. Die Ableitungen einer Graph-Grammatik beginnen dabei mit einem Startgraphen und enden in Graphen, die eine terminale Markierung aufweisen.

Es werden nur Regeln aus der Grammatik benutzt, um Graphen abzuleiten. Die Basisidee von Graphersetzung ist die Ersetzung eines Graphen durch einen anderen. Die Ersetzungsvorschrift wird in einer Regel r: N :L ---> R fest gehalten, in der N, L und R Graphen sind. L wird als linke Seite und R als rechte Seite der Regel bezeichnet, N als die negative Anwendungsbedingung.

Eine Anwendung der Regel auf einen Graphen G bedeutet, dass ein Vorkommen von L durch R ersetzt wird, falls in dem Vorkommen von L die Bedingung N nicht erfüllt ist. Die regelbasierte visuelle Sprache "Attributed Graph Grammar" (AGG) unterstützt einen algebraischen Ansatz zur Graphersetzung. AGG liefert sowohl eine graphische Oberfläche als auch eine Graphersetzungs-Engine, die in Java-Anwendungen integriert werden kann.

Im Rahmen des Fopras sollen sowohl die Regeln als auch die Oberfläche des Backgammon-Spiels mit einer Graph-Grammatik in AGG bzw. Java implementiert werden.

Bearbeiter: offen
Aufgabensteller: Prof. Dr. Wirsing
Betreuer: Shadi al-Dehni
Voraussetzungen: Kenntnisse in Java