Описание программы-эмулятора алгоритмов Маркова

Тренажёр «Нормальные алгорифмы Маркова» это учебная модель универсального исполнителя, предложенного в 1940-х годах А.А. Марковым для уточнения понятия алгоритма. Марков предположил, что любой алгоритм может быть записан в виде нормального «алгорифма» (учёный считал, что правильно произносить это иностранное слово именно так). Позднее было доказано, что нормальные алгорифмы Маркова эквивалентны по своим возможностям другим универсальным исполнителям: машине Тьюринга и машине Поста.

Нормальный алгорифм задает метод преобразования строк с помощью системы подстановок. Каждая подстановка состоит из слова-образца и слова-замены, разделенных цепочкой символов «->». На каждом шаге замены подстановки просматриваются по порядку сверху вниз, и выполняется первая из них, которая подошла: первое найденное слово-образец рабочей строки заменяется на слово-замену.

Рис. 15. Программный эмулятор алгоритмов Маркова

Слова слева и справа от знака «->» могут быть (а могут и не быть) заключены в апострофы или двойные кавычки. Следующие подстановки равносильны и определяют замену буквы «а» на сочетание «бв»:

а -> бв

'а' -> 'бв'

"а" -> "бв"

'а' -> "бв"

Левая часть (слово-образец) может отсутствовать, в этом случае слово-замена ставится в самое начало рабочего слова. Обычно такая замена должна стоять последней в списке подстановок (иначе происходит зацикливание).

Правая часть подстановки тоже может отсутствовать (при стирании образца).

Символ «.» после слова-замены обозначает терминальную подстановку, после которой выполнение алгоритма заканчивается. Например:

'а' -> 'б'. заменить «а» на «б» и остановить программу

* ->. стереть знак «*» и остановить программу

В верхней части программы находится поле редактора, в которое можно ввести условие задачи в свободной форме.

Система постановок, задающая нормальный алгорифм Маркова, набирается в виде таблице в нижней части окна программы.

Программа может выполняться непрерывно (F9) или по шагам (F8). Команда, которая сейчас будет выполняться, подсвечивается зеленым фоном. Скорость выполнения регулируется с помощью меню Скорость.

Задачи можно сохранять в файлах и загружать из файлов. Сохраняется условие задачи, исходное слово и система подстановок.

Протокол работы алгоритма, в котором показаны все последовательные замены, вызывается при нажатии клавиш Ctrl+P.

Содержание работы

Запустить программу-эмулятор алгоритмов Маркова. Ознакомиться с работой эмулятора и набором команд. Воспроизвести (не сохраняя в файл) предложенные выше примеры. По указанию преподавателя выбрать варианты из папки \..Example программы-эмулятора. По завершении работы результаты сохранить в файл.