Markov-Algorithmus zum Halbieren von Strichlisten

Hallo,
ich soll Regeln für einen Markov-Algorithmus aufstellen mit diesem es möglich ist Strichlisten zu halbieren, Beispiel:
IIIIII => III
IIIII => II-

Die Zeichenmenge ist also {I,-}

Ich habe schon unzählige Regeln aufgestellt, aber bisher hatte ich immer das Problem, dass der Algorithmus, dann nicht bei der Hälfte stehen bleibt, sondern dass er weiterläuft und man am Ende weniger als die Hälfte da stehen hat.

Mein bisher bester Ansatz:
Regeln:
(1) III => II-
(2) -I => I-
(3) -- => -
(4) I- =>. -

Ableitung:
IIIIII => II-III => II-II- => III-I- => II--I- => II-I-- => III--- => II---- => III-- => II--- => II-- => III (jetzt sollte er stehen bleiben, aber man kann ja jetzt wieder Regel 1 anwenden)

IIIII => II-II => III-I => II--I => II-I- => III-- => II--- => III- => II-- => II- (jetzt sollte er stehen bleiben, aber man kann hier ja noch Regel 4 anwenden)

Könnt ihr mir helfen?

Gruß Informatiker

pumuckl

Da du keinerlei Angabe machst, wann der algorithmus abzubrechen ist, wird das auch immer weitergehn, auch wenn die Strichliste schon halbiert ist. Schließlich ist eine halbierte Strichliste immernoch eine Strichliste, durch die sich der Algorithmus immer weiter durchfrisst. Ohne Hilfskonstrukte wirds also kaum zu schaffen sein

Wenn du darfst, dann füge ein "Lesekopf"-Zeichen ein, damit wird das Ganze recht simpel:

Setze Anfangs ein ')' vor deine Strichliste
Regeln sind dann:

)II -> I)
)I -> -)
) -> ε

Und fertig.
Beispiel:

)IIIIII -> I)IIII -> II)II -> III) -> III

Das ist brilliant

Sowas zu konstruieren hab ich zwar schon versucht, aber auf die Idee ein Lesekopf zu basteln noch nicht.

Danke!