3. Пример 1: использование алгоритма Маркова для преобразований над строками

Алфавит:

{ а...я, А...Я, пробел, точка }

Правила:

1. А → апельсин

2. кг → килограмм

3. М → магазинчике

4. Т → том

5. магазинчике →• ларьке (заключительная формула)

6. в том ларьке → на том рынке

Исходная строка:

Я купил кг Аов в Т М.

При выполнении алгоритма строка претерпевает следующие изменения:

1. Я купил кг апельсинов в Т М.

2. Я купил килограмм апельсинов в Т М.

3. Я купил килограмм апельсинов в Т магазинчике.

4. Я купил килограмм апельсинов в том магазинчике.

5. Я купил килограмм апельсинов в том ларьке.

На этом выполнение алгоритма завершится (так как будет достигнута формула № 5, которую мы сделали заключительной).

4. Пример 2: преобразование чисел

Данный алгоритм преобразует двоичные числав «единичные» (в которых записью целого неотрицательного числа N является строка из N палочек). Например, двоичное число 101 преобразуется в 5 палочек: |||||.

Алфавит:

{ 0, 1, | }

Правила:

1. |0 → 0||

2. 1 → 0|

3. 0 → "" (пустая строка)

Исходная строка:

101

Выполнение:

1. 0|01

2. 00||1

3. 00||0|

4. 00|0|||

5. 000|||||

6. 00|||||

7. 0|||||

8. |||||

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

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

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

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

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

а -> бв

'а' -> 'бв'

"а" -> "бв"

'а' -> "бв"

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

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

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

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

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

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

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

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

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

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