Брачная не статья. Алгорифмы Маркова. Часть 2.

Добрый день/вечер/ночь. Вы этого не просили и даже Мынка нас не уговаривал, но вот. Мы снова тут. И мы поговорим про Нормальные Алгорифмы Маркова, да да именно про алгориФмы. Ну что, готовы посмотреть туда, куда смотрит Мынка?

Начало

Будем рассматривать алфавитные операторы вида

(то, есть входной и выходной алфавиты совпадают).

При этом, это не ограничивает общность:

Способ задания оператора Γ будет основан на элементарных действиях двух типов:

1. распознаватель вхождения: проверяет, является ли слово α подсловом слова β;
2. оператор подстановки

заменяет вхождение слова

в слове

на

в итоге получаем слово

Схема (система подстановок) нормального алгорифма Маркова задаётся следующим образом:

1. выписывается (обычно в столбик) упорядоченная последовательность операторов подстановки;
2. в последовательности могут быть выделены заключительные подстановки; обозначаются

Определение. Нормальным алгорифмом Маркова в алфавите A называется пара объектов (A, S), где A — алфавит, S — система подстановок.

Алгорифм работает в соответствии с предписанием о порядке применения подстановок к заданному слову β:

1. Просмотреть систему подстановок с самого начала и найти первую по порядку применимую подстановку

, т. е. такую подстановку, левая часть которой является подсловом слова β.

2. Если применимой подстановки не найдено, то выход, ответ: β.

3. Найденная подстановка применяется к слову β, а именно: первое (самое левое) вхождение

в β заменяется на

4. Если применена заключительная подстановка, то выход, ответ: β, иначе переход к п. 1.

Обратим внимание:

1. на каждом шаге возвращаемся к началу системы подстановок и к началу слова;
2. алгорифм завершает свою работу в двух случаях:
   а) если ни одна подстановка не применима;
   б) если применена заключительная подстановка.

Рассмотрим пример:

Остановились, так как ни одна подстановка не применима.

Другой пример:

Остановились, так как применили заключительную подстановку.

А теперь, хотите попробовать сделать это сами? Если да, то вот вам задание, если нет, то ответ ниже.

Решение довольно простое:

Но если мы столкнёмся с такой задачей:

Задача подводка(а вы знали что если заменить в слове подводка одну букву будет подлодка?). A = {0, 1}; Надо инвертировать булев вектор.

То мы столкнёмся не только с задачей, но и с трудностями, ведь решение которое первое приходит на ум

является неверным, так как подстановки применимы всегда.

Что же тогда сделать? — спросите вы. И я отвечу — расширим алфавит, товарищи.

И теперь запишем систему подстановок:

И возьмём любой булев вектор и получим:

Как вы могли заметить роль ∗ — разделяет «пройденную» и «не пройдённую» части слова.

Заметим особенность подстановки λ → α: она всегда применима. Поэтому если система подстановок содержит такую подстановку, то:

1. она должна стоять последней,
2. в системе должны быть заключительные подстановки.

Нормальный алгорифм Маркова, в системе подстановок которого используются дополнительные (не входящие в алфавит A) символы, называется алгорифмом над алфавитом A;
Заметим что при этом, исходные данные и результат работы алгоритма — по-прежнему слова в алфавите A.

А теперь рассмотрим более сложные интересные вещи, а именно композиции.

Определение. Композиции алгоритмов — получение из известных алгоритмов новых, более сложных.

Существуют 4 основных способа композиции.

Суперпозиция или последовательная композиция(Шредингера на вас нет)

Дано:

Алгоритм Z = Y (X) — суперпозиция алгоритмов X и Y , если

Пример:

Что делает композиция Y (КОП)?

, где КОП — копирующий нормальный алгорифм Маркова, который для любого числа в естественном коде

получает слово

Ответ прост. Композиция Y (КОП) — умножение на 2 числа в естественном коде.

Объединение или параллельная композиция

Дано:

Алгоритм Z = X||Y — объединение алгоритмов X и Y , если

Пример:

Что делает композиция E||X?

Ответ не сложный E||X = КОП

Разветвление

Разветвление — композиция трёх алгоритмов.

Дано:

Алгоритм W — разветвление алгоритмов X, Y и Z, если

Итерация или повторение

Одни и те же действия повторяются многократно, пока не получим результат, обладающий свойством C.

Дано:

НАМ X, распознающий НАМ Z.

Алгоритм T — итерация алгоритмов X и Z, если для исходного слова α он строит последовательность слов

Тогда

.

Итог.

На этом вторая часть нашего цикла заканчивается. И именно поэтому, мы не можем вас оставить без задания.

Задание:

A = {|, ∗}; Построить КОП не используя композиции.

На этом всё. Надеемся вам было интересно.

Если у вас появились вопросы мы с радостью ответим на них в комментариях или сообщениях группы.