Алгоритм Маркова для f(x)=x/2

[Sergio471]

Помогите, пожалуйста, построить алгоритм Маркова для функции f(x)=x/2. Если x нацело не делится, то округление идет в большую сторону. Число неотрицательное и записывается в 10-ой системе счисления, т.е. алфавит={0..9}.
Пример: f(0)=0; f(1)=1; f(13)=7; f(20)=10.
Заранее спасибо.

[Xaositect]

А что не получается-то?
$f(10x + y) = 5x + f(y) = 10f(x) + f(y) - 5\cdot[x\mod 2]$
Значит, вставляем в начало бегщий символ и идем слева направо, обрабатываем по приведенной выше формуле.
Надо только аккуратно правила выписать.

[Sergio471]

Интересненько. Но вы не могли бы помочь именно в написании таблицы правил замещения. Мне нужно это на компьютере реализовать, чтобы показывались пошагово замещения, для чего, собсно, табличка и нужна:)