Задача

Разработать в среде Excel две модели - машину Тьюринга и нормальный алгоритм Маркова (НАМ) - для выполнения операции замены над строкой из символов алфавита A = {a, b, c}.

Условие:

• Входные данные: произвольная строка P, состоящая из символов a, b, c.
• Необходимо: заменить в строке P каждое вхождение подстроки ab на символ c.
• Результат: строка после применения правила замены.

Требования к реализации:

• Решение должно быть представлено двумя разделами (листами или частями Excel-файла):
  1. Машина Тьюринга - описание алфавита, состояний, правил перехода (вида «текущее состояние - обозреваемый символ - команда»), а также демонстрация работы на примере с пошаговым отслеживанием состояния ленты и УУ.
  2. Нормальный алгоритм Маркова (НАМ) - формирование списка схемы (включительно замещающие и заключительные формулы) и демонстрация их последовательного применения до полной остановки алгоритма.
• Таблицы должны быть оформлены по образцу методички (каждое правило указано в отдельной строке, схемы иметь номера шагов, итоговое состояние ленты/строки ясно отображено).
• Задание должно полностью выполняться в Excel (использовать макросы допускается, но можно реализовать и моделирование логико-формальными таблицами).
• Проверить работоспособность на тестовых строках (например: 'a b a b b', 'a b a c b', 'b b b a b', пустая строка).

Ожидаемый результат:

Готовая таблица (Лист «Тьюринг» и Лист «НАМ») с ясными заголовками, примерами переходов, выделенными начальным и конечным состоянием. Каждый метод надо проиллюстрировать на отдельной строке-примере.