REPLACE wurde als Aufgabe in Runde 2 beim BWInf 1992 gestellt.
Die Aufgabenstellung konnte ich in der Oberprima gut verwenden(theoretische Informatik)

Die Programmiersprache REPLACE kennt als Datentyp nur Zeichenketten und
als Operation nur kontextabhängiges Ersetzen. Sie ist wie folgt definiert:

Syntax :

<Programm> ::= <Ersetzungsfolge> (,)
<Ersetzungsfolge> ::= <Ersetzung> | <Ersetzungsfolge> <Ersetzung>
<Ersetzung> ::= ( <alt> , <neu> )
<alt> ::= <Zeichenkette>
<neu> ::= <Zeichenkette> | <leere Zeichenkette>
<leere Zeichenkette> ::=
<Zeichenkette> ::= <Zeichen> | <Zeichenkette> <Zeichen>
<Zeichen> ::= <irgendein ASCII-Zeichen außer ',' und ' '> statt Leerzeichen ist '_' besser zu sehen

Semantik :

Die Eingabezeichenkette wird zur aktuellen Zeichenkette.
Diese wird nach folgender Vorschrift verändert :
Es wird die erste <Ersetzung> in der <Ersetzungsfolge> gesucht, für die
<alt> eine Teilzeichenkette der aktuellen Zeichenkette ist. War die
Suche erfolgreich, wird die gefundene Teilzeichenkette durch <neu> von
<Ersetzung> ersetzt. Ist die Suche nicht eindeutig, wird immer die am
weitesten links stehende Teilzeichenkette genommen.(Linksherleitung!)
Die Vorschrift wird solange angewandt, wie in der aktuellen Zeichen-
kette eine Teilzeichenkette gefunden wird, die mit Hilfe einer
<Ersetzung> verändert werden kann. Dann wird die aktuelle Zeichenkette
zur Ausgabezeichenkette.

Beispiel :

Das Replace-Programm : (aa,b) (ba,a) (bc,a) (c,start) (d,) (b,finish) (,)
Die Eingabezeichenkette : abcabcd

aktuelle Zeichenketten : abcabcd
aaabcd
babcd
abcd
aad
bd
b
finish

Die Ausgabezeichenkette : finish

Mehr Infos unter de.wikipedia.org/wiki/Markow-Algorithmus
Ein Markow-Algorithmus ist ein deterministisches Textersetzungssystem mit endlich vielen Regeln.
Der Interpreter verarbeitet definierte Ersetzungsfolgen.

Beispiele sind im Ordner <ReplaceProgramme>
Aufgaben für Tüftler:
Hex in Bit Eingabe: z.B.: ?$FA9E2
Teilbarkeit von natürlichen Zahlen auf 3 oder 9 Eingabe: z.B.: ?564387
Dualnachfolger Eingabe: z.B.: ?L0LL
Quersumme ermitteln Eingabe: z.B.: ?6754334
Viel Spaß beim Knobeln
Gruß Fiete