Grammatiken mit Mathematica

Stacks Image 617

Die Ersetzungsregel einer Grammatik kann man recht einfach mit den Ersetzungsregeln von Mathematica nachbilden. Wir werden hier die Funktion StringReplace dazu nutzen. Als erstes, zum Einstieg sozusagen, werden wir uns dem Problem so nähern, wie man es in der "klassischen" Programmierung, etwa in Java oder C, tun würde. Wir werden dann aber sehr schnell die Mächtigkeit der Mathematica-eigenen Befehle sehen, mit denen das o.g. Problem recht schnell "erschlagen" werden kann.

%[if edit]%

Collapsible Stack

Drag a stack here.

%[endif]% %[if !edit]% %[endif]%
Die Anwendung mehrerer Ersetzungen hintereinander ist auch kein Problem, da StringReplace auch eine Liste von Ersetzungen annehmen kann.

Allerdings ist das nicht ganz das was wir hier brauchen, schließlich soll die zweite Ersetzung ja auf den String angewandt werden, der als Ergebnis der ersten Ersetzung entstanden ist. Dies ist mit der Funktion ReplaceAll (/.) nicht so einfach zu bewerkstelligen, da nach der ersten Ersetzung ja der String “SA” vorliegt, auf den die Regel “S”->”SS” keine Wirkung hat. Mit StringReplace ist dies jedoch problemlos möglich:

%[if edit]%

Collapsible Stack

Drag a stack here.

%[endif]% %[if !edit]% %[endif]%
%[if edit]%

Collapsible Stack

Drag a stack here.

%[endif]% %[if !edit]% %[endif]%
Nun kann man recht leicht ermitteln, wie das Ergebnis der, sagen wir mal dreifachen, Anwendung der Regeln auf das Startsymbol "S" ist. Zunächst besorgen wir uns alle Möglichkeiten die Regeln anzuwenden, was mit der Funktion Tuples recht einfach ist.

Jede dieser Möglichkeiten muß nun auf das Startsymbol angewandt werden. Zuvor muß jedoch jede einzelne Ersetzungsregel in eine Liste quasi eingepackt werden, um die Funktion StringReplace später einfacher anwenden zu können. Das zweite Codebeispiel zeigt, wie das geht

Der hier angegebene Parameter {2} bewirkt, daß der Befehl auf die Listenelemente der Ebene 2 angewendet werden. Zur Anwendung dieser Ersetzungslisten verwenden wir eine Funktion die jede Ersetzungsliste auf das Startsymbol anwendet
%[if edit]%

Collapsible Stack

Drag a stack here.

%[endif]% %[if !edit]% %[endif]%
%[if edit]%

Collapsible Stack

Drag a stack here.

%[endif]% %[if !edit]% %[endif]%
Die nebenstehende Funktion baut all diese Bestandteile zusammen. Man muß aber zugegeben, das hat mit Mathematica nicht viel zu tun, sondern ist im Grunde klassischer Programmierstil (und sieht in Mathematica einfach häßlich aus). Funktionieren tut es aber....
%[if edit]%

Collapsible Stack

Drag a stack here.

%[endif]% %[if !edit]% %[endif]%
Der wesentliche Nachteil dieses klassischen Ansatzes ist, daß man die mächtigen iterativen Funktionen von Mathematica, wie etwa Nest und NestList, hier nicht ohne Weiteres einsetzen kann. Mathematica besitzt mächtige Funktionen, die hier viel besser eingesetzt werden können als obiger iterativer Ansatz.
Aber das ist nicht das einzige Problem. Wir arbeiten hier mit Regeln, brauchen aber eigentlich Strings. Dieser Nachteil kann aber leicht behoben werden, indem wir generell mit Strings arbeiten. Was wollen wir eigentlich?
Auf einen Startstring, oder eine Menge von solchen Strings, soll eine Reihe von Ersetzungsregeln angewendet werden. Mehr nicht. Also brauchen wir nur eine Funktion, die eine Liste von Regeln auf eine Menge (Liste!) von Strings anwendet. Nichts leichter als das, wir brauchen dazu nicht einmal zu programmieren, alles was wir brauchen bringt Mathematica bereits mit, nämlich die Funktion StringReplaceList
%[if edit]%

Collapsible Stack

Drag a stack here.

%[endif]% %[if !edit]% %[endif]%
Bei dieser Lösungsvariante ist es nun eben möglich die Mathematica Funktion NestList anzuwenden, die den Hauptteil der Arbeit im vorliegenden Fall übernimmt.

Nun bauen wir das Ganze noch ein in eine - sehr übersichtliche - Mathematica Funktion. Die produzierten Terminalstrings kann man dann einfach über eine Select Anweisung ausfiltern, was in diesem Falle lediglich das Ergebnis {, ab} liefern würde. Vier Iterationen sind hier einfach zu wenig, um eine gewisse Menge an Terminsalstrings zu erzeugen.

Nun schauen wir uns an, wie man damit beispielsweise den "Klassiker" unter den Grammatiken, die Grammatik die die Klammerausdrücke produziert, verifizieren kann.
%[if edit]%

Collapsible Stack

Drag a stack here.

%[endif]% %[if !edit]% %[endif]%
%[if edit]%

Collapsible Stack

Drag a stack here.

%[endif]% %[if !edit]% %[endif]%
%[if edit]%

Collapsible Stack

Drag a stack here.

%[endif]% %[if !edit]% %[endif]%

Kontextsensitive Grammatiken

Kontextsensitive Grammatiken sind deutlich komplexer, als die eben betrachteten Beispiele. Dies ist insofern nicht verwunderlich, als das kontextsensitive Grammatiken ja nun einmal auch Sprachen erzeugen können, die für kontextfreie Grammatiken nicht erreichbar sind.

Ich betrachte hier ein spezielles Beispiel einer kontextsensitiven Grammatik. Es ist die Grammatik zur Sprache: L = {a^nb^nc^n}
in der rechts stehenden Abbildung sind die von der betrachteten Grammatiken erzeugten Terminalstrings aufgezeigt. Die hier abgebildeten Strings sind alle Terminalstrings die in bis zu 20 Iterationen aus den Produktionen der Grammatik erzeugt wurden. Die "Ausbeute" ist in der Tat gering, wenn man bedenkt, daß bei 20 Iterationen mehr als 130.000 Strings erzeugt wurden.
Mehr dazu steht in den Dokumenten, die im Downloadbereich dieser Seite verfügbar sind.

Stacks Image 701
Stacks Image 687

Download

Die hier zum Download zur Verfügung gestellten Materialen gehen über das hinaus was im Text der Webseite zu sehen ist.

Stacks Image 674