Эмулятор нормальных алгоритмов Маркова

Входное (выходное) слово:

Краткие теоретические сведения

Нормальные алгоритмы Маркова (далее — НАМ), введенные советским математиком А. А. Марковым, представляют собой класс алгоритмов, применимых к словам некоторого алфавита. Каждый НАМ определяется указанием алфавита, в котором он действует, и схемы НАМ. Алфавитом НАМ может служить любой конечный алфавит A. Формулой подстановки в алфавите A называется выражение типа p → q (простая подстановка, в эмуляторе обозначена как ->) или p ↦ q (заключительная подстановка, в эмуляторе обозначена как =>), где p и q — некоторые слова в алфавите A, называемые, соответственно, левой и правой частями формулы подстановки. Каждый НАМ в алфавите A имеет конечное число формул подстановки. Их записывают в виде списка, который называется схемой алгоритма.

Применение НАМ к некоторому слову S заключается в следующем. В списке формул подстановки ищется первая из тех формул, в которой левая часть входит в S. Находится 1-е вхождение левой части формулы в S и вместо этого вхождения подставляется правая часть формулы. Получается новое слово S'. Cо словом S' производятся те же действия и т.д.

Данный процесс обрывается в 2-х случаях:

• к очередному слову применена одна из заключительных формул подстановки;
• в слово не входит ни одна из левых частей формул подстановки.

Получаемое последнее слово является результатом применения НАМ к исходному слову S.

Примеры на составление нормальных алгоритмов Маркова

Пример 1.
В произвольном слове, состоящем из букв {a, b, c}, все подряд стоящие одинаковые буквы заменить одной буквой (например, слово «abbbcaa» преобразовать в «abca»). Схема НАМ. имеет вид:

Применение этой схемы с слову «abbbcaa» последовательно даст слова: «abbbca», «abbca» и «abca», после чего выполнение НАМ завершится. Для проверки данного алгоритма загрузите его текст в эмулятор.

Пример 2.
Удвоить слово, состоящее из одинаковых символов (для определенности — «x»). Т.е. слово «x» надо преобразовать в «xx», слово «xx» — в «xxxx» и т.д.

Схема НАМ для этого примера намного сложнее, чем для примера 1. Нельзя написать x → xx, т.к. в этом случае на каждом шаге НАМ к слову будет добавляться символ «x» и этот процесс будет бесконечным. Необходимо контролировать удвоение каждого символа слова так, чтобы каждый символ удвоился только один раз. Для это введём маркер, с помощью которого будем обеспечивать контекст применения удваивающего правила.

Последнее правило вводит «маркер» '*' (или «курсор»), который с помощью первого правила «перескакивает» через текущий символ слова и удваивает его. Применение этой схемы, например, к слову «xx» последовательно даст слова: (3) «*xx», (1) «xx*x», (1) «xxxx*», (2) «xxxx» (в скобках указан номер применяемой формулы подстановки).

Пример 3.
Дано слово в алфавите {a, b, c}. Упорядочить буквы входного слова в лексикографическом порядке

Типовые задачи, решаемые студентами 110 и 111 группы на семинарах