Google
 
Главная2-й курс3-й курс4-й курс5-й курсСпецкурсыСсылкиКарта(версия для печати)

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

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

Правила:

Максимальное количество обрабатываемых правил: 20.
Максимальное количество циклов выполнения: 500.

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

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

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

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

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

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

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

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

1.aaa
2.bbb
3.ccc

(загрузить в эмулятор)

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

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

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

1.*xxx*
2.*
3.*

(загрузить в эмулятор)

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

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

(загрузить в эмулятор).

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