Нормальные алгорифмы Маркова (НОК).

На доске мелом написана строка вида: 11..1*11..1 (слева от звёздочки N единиц, справа – M; N,M – натуральные числа; N,M=1,2,…).
Ваша задача придумать такие правила, после применения которых на доске было бы записано число вида: 11..1 (число единиц равно НОК(N,M) – наименьшее общее кратное чисел N, M).
i-ое правило имеют следующий вид: S_i->P_i, где S_i и P_i некоторые строки (возможно пустые). Строки S_j и P_j могут содержать любые символы, а не только «1» и «*».
Правила применяются следующим образом: ищем первое правило, в котором левая часть (до ->) присутствует в строке на доске. Пусть это правило S_j->P_j. Стираем первое вхождение S_j в строке на доске и в образовавшееся пустое место записываем P_j (считаем, что мы всегда можем вписать сколько угодно длинную строку в сколь угодно малое пространство). Повторяем описанные выше действия до тех пор, пока хоть одна из левых подстрок правил входит в строку, записанную к тому моменту на доске. То есть на каждом этапе мы начинаем просматривать правила, начиная с самого первого, и заменяем только первое вхождение S_j в строке на доске (даже если их больше).

Пример:

a) Пусть на доске записано строка такого же вида, как и в условии выше. Тогда правило:
1) *-> (звёздочка заменяется на «пусто»)
приводит к сумме чисел N и M на доске.

11*111
11111

b) Пусть на доске записана строка такого же вида, как и в условии выше. Тогда правила:
1) 1*1->*
2) *-> (звёздочка заменяется на «пусто»)
приводят к модулю разности чисел N и M.

11*111
1*11
*1
1

Формат ответа:

вы должны привести последовательные правила вида (S_i->P_i).

Критерий оптимальности

количество правил. Чем меньше, тем лучше.