Das vom sowjetischen Mathematiker Andrei Markow entwickelte Verfahren zur symbolischen Datenverarbeitung verwendet als einziger Programmierbaustein Substitutionsregeln. Mit dem Verfahren lassen sich zahlreiche Probleme, z.B. die Konjugation und Deklination natürlicher Sprachen effizient lösen. Anders als im Original verwenden wir eine mit regulären Ausdrücken¹⁾erweitere Form. Das ermöglicht es mit weniger Code schon komplexere Aufgaben zu lösen.

Ein Markow-Algorithmus (MA) ist eine geordnete Menge von Substitutionsregeln. Die Regeln haben jeweils die folgende Form:

Auf dem zu verarbeitenden Eingangswort findet nach dem Starten des Programms eine Suche über das Suchmuster der ersten Regel statt. Ist dieses im Eingangswort enthalten, wird eine der Regel entsprechende Substitution durch das Ersetzungsmuster ausgelöst. Das Eingangswort wird von links nach rechts durchsucht. Somit wird bei einem Mehrfachvorkommen des linken Wortes der Regel stets das am weitesten links stehende Vorkommen substituiert. Bei der Verwendung des Modifikators g werden alle gefundenen Muster geleichzeitig substituiert.

Ist die oben beschriebene Suche erfolglos, wird zur nächsten Regel übergegangen. Kann unter Einbeziehung aller weiteren Regeln keine Substitution vorgenommen werden, so ist der Algorithmus beendet. Auch die Anwendung einer terminierenden Regel führt zu dessen Beendigung. Terminierende Regeln sind am ! am Schluss zu erkennen. Wurde mittels einer nicht terminierenden Regel substituiert, so beginnt der gesamte Ablauf unter Berücksichtigung des geänderten Wortes erneut. Kann keine passende Substitutionsregel gefunden werden, stoppt das Programm ebenfalls.

Der Markow-Algorithmus wandelt einen vorgegebenen Text nach vorgegebenen Regeln um. Diese Regeln bestehen ausschliesslich aus Ersetzungsmustern. Beispielsweise schreibt man für die Anweisung, dass die Ziffernfolge '010' durch die Ziffernfolge '111' ersetzt werden soll, folgende Regel:

/010/111/

Ein Markow-Algorithmus kann natürlich aus vielen solchen Anweisungen bestehen. Diese werden dann nach folgendem Schema immer wieder durchgearbeitet, bis es nicht mehr weitergeht:

1. Gehe alle Regeln der Reihe nach durch.
2. Wenn eine Regel irgendwo anwendbar ist, so führe sie an der linkesten Stelle aus, wo sie auf den Text zutrifft.
3. Starte danach von Neuem.

Einigen Regeln kann man mit einem Terminierungs-Symbol die Anweisung mitgeben, dass der Algorithmus, sobald er diese Regel ausführt, danach automatisch stoppt. Sie werden durch einen Ausrufezeichen versehen.

/010/111/ !

Diese simplen Regeln reichen oft nicht für alle Probleme aus. Was noch hinzukommt sind Marker. Dies sind Buchstaben oder Symbole, die für die Ausführungsdauer in den Text eingearbeitet werden können, jedoch vor Terminierung wieder entfernt werden müssen. Meistens werden dafür die Buchstaben des griechisches Alphaets verwendet:

α β γ δ ε ζ η θ ι κ λ μ ν ξ ο π ρ ς σ τ υ φ χ ψ ω ϑ ϒ ϖ

Das folgende Beispiel soll eine solche Anwendung illustrieren. Die folgenden Ersetzungsregeln bewirken, dass das linkeste 0 in einer Binärzahl ganz nach hinten verschoben wird:

Eingabe

01010001111

Ausgabe

10100011110

Algorithmus

/π1/1π/
/π0/0π/
/π/0/ !
/0/π/ 

Variante

Da die Substitutionsregeln als reguläre Ausdrucke interpretiert werden, hat man die Möglichkeit zahlreiche Probleme wie das obige, unter Verwendung von Gruppen, eleganter lösen.

/(0)(.*)/$2$1/ !

Die Substitutionsregeln /Suchmuster/Ersetzungsmuster/ lassen sich mit Modificatoren ergänzen. Siehe oben.

g

wendet die Ersetzungsregel global an, also auf alle Textbausteine, die ersetzt werden

m

Mehrzeilenmodus. Im Mehrzeilenmodus bekommen ^ und $ eine neue Bedeutung. ^ steht neue für Zeilenanfang und $ steht neu für Zeilenende anstelle von Textanfang und -ende.

i

insensitiv gegenüber Gross- und Kleinschreibung

Das folgende Schema veranschaulich die Anwendung der Modifikatoren. Für weiterführende Informationen: siehe selfhtml.org

Unter http://exorciser.ch/dev/rema.html findest Du eine Arbeitsumgebung für erweiterte Markov Algorithmen.

• Aufgaben Serie A
• Aufgaben Serie B
• Aufgaben Serie C