Алгоритм Маркова

[Medvedica8898]

Помогите решить задачку, пожалуйста. Нужно составить алгоритм Маркова в котором удаляется вторая половина слова, состоящего из букв ab (если слово нечетное, удаляем большую часть)
Например: есть слово abbaba, после выполнения программы должно получиться abb. Если же дано слово aabaaba, должно получиться aab.

[Black Fregat]

У алгоритмов Маркова, подобных тому, о котором Вы пишете, есть одна неприятная особенность: очень тяжело отличить начальное состояние строки от конечного. Грубо говоря, если делать в чистом виде алгоритм, переводящий abbaba -> abb, то те же самые правила в какой-то момент начнут кромсать уже этот финальный abb.

Самое простое решение этой проблемы - пометить начальную строку каким-то дополнительным символом, например abbabaZ -> abb

Тогда правила могут быть, например, такими:

aZ->Zay
bZ->Zby
Z->
ya->ay
yb->by
yy->x
y->x
ax->
bx->