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

a0 → 0a (где a — любой бит, 0 или 1)
a1 → 1a
0# → #0
1# → #1
0#0 → #0
1#0 → #1
0#1 → #1
1#1 → 0c (если c — текущий перенос, начинаем с 0)
0c#0 → #0c
1c#0 → #1c
0c#1 → #1c
1c#1 → 1c
c0 → 0c
c1 → 1c
#c → #1
Пример алгоритма:

 1. a0 → 0a 
2. a1 → 1a 
3. 0# → #0 
4. 1# → #1 
5. 0#0 → #0 
6. 1#0 → #1 
7. 0#1 → #1 
8. 1#1 → 0c 
9. 0c#0 → #0c 
10. 1c#0 → #1c 
11. 0c#1 → #1c 
12. 1c#1 → 1c 
13. c0 → 0c 
14. c1 → 1c 
15. #c → #1 
 

Пример работы алгоритма:
Вход: 11#10

Применение правил:

1 → # → 1 → 1 (добавляем оба числа)
11#10
Применяем правила для сложения каждого бита, начиная с младшего разряда.
0# → #0
1#0 → #1
Применяем правило переноса при сложении 1 и 1.
Таким образом, пошагово применяя правила, можно реализовать сложение двух чисел в двоичной системе с помощью нормального алгоритма Маркова.

Нормальный алгоритм Маркова для сложения двоичных чисел
Ввод: Два двоичных числа, разделенных знаком "+", например: "101+11".
Выход: Двоичное число, являющееся суммой входных чисел.
Алфавит: {0, 1, +, =}
Схема подстановки:
1. 0+0 -> +0
2. 1+0 -> +1
3. 0+1 -> +1
4. 1+1 -> +01
5. += -> =
6. **+ -> ** (удаляем "+" в начале строки)
Описание работы алгоритма:
1. Инициализация: Алгоритм начинает работу с входной строки, содержащей два двоичных числа, разделенных знаком "+".
2. Сложение поразрядно: Алгоритм последовательно применяет правила подстановки 1-4, двигаясь справа налево.
o Правила 1-3 обрабатывают случаи сложения битов без переноса.
o Правило 4 обрабатывает случай сложения битов с переносом, добавляя "1" перед результатом.
3. Обработка переноса: Если в результате сложения образовался перенос (правило 4), алгоритм продолжает применять правила 1-4 к следующим разрядам, пока перенос не будет учтен.
4. Завершение: После обработки всех разрядов алгоритм применяет правила 5-6 для удаления знака "+" и получения окончательного результата.
Пример:
Рассмотрим пример сложения чисел "101" и "11":
1. 101+11 (начальная строка)
2. 10+011 (правило 4)
3. 1+1011 (правило 2)
4. =01011 (правило 5)
5. 01011 (правило 6)
Таким образом, алгоритм корректно вычислил сумму: 101 (2) + 11 (2) = 1011 (2).