Теория алгоритмов. Нормальные алгоритмы Маркова

[Карто]

Нормальный алгоритм Маркова в алфавите А = {1,*,a,b} задан следующей системой ориентированных подстановок:

1) *11 -> a*1
2) *1 -> a
3) 1a -> a1b
4) ba -> ab
5) b1 -> 1b
6) a1 -> a
7) ab -> b
8) b -> 1
9) 1 -> 1.

Выполняя пошаговое исполнение алгоритма над словом 1111…111 выясните, какую функцию она вычисляет.