Алгоритмы Маркова. Нормальные алгорифмы Маркова

1. АЛГОРИТМЫ МАРКОВА

Ефремова Е.Г. гр. 551

2. Нормальные алгорифмы Маркова

3. Нормальные алгорифмы Маркова

Основная операция при работе
алгоритмов Маркова –
переработка слов в некотором
алфавите А.

4. Нормальные алгорифмы Маркова

Алгоритм представляет собой
совокупность строк
определенного вида, порядок
строк имеет важное значение.
Формат строки:
{ai}→{bj} [•]

5. Включение слова в другое слово

А = {а, б, в, ... я}.
Слово Р = (параграф),
Подслова Q = (ра), М = (граф).

6. Частный случай марковских подстановок

Подстановка пустых слов
(^,Q), (Р, ^), (^, ^), где ^ = (...).

7. Пример

R = (параграф), P = (ра);
(R,P), (ра → лил);
R → P‘ = (палилграф).

8. Определение

Пара (P,Q) называется формулой
марковской подстановки. Слово P
называется левой частью формулы,
слово Q – правой.
P→(•) Q – заключительная подстановка;
P→ Q – подстановка не является заключительной

9. Определение

Упорядоченный набор формул
марковских подстановок
называется схемой нормального
алгоритма Маркова заданного над
алфавитом А:
R1 → (•) Q
R2 → Q
или
…………..
{Р2 → (•) Q

10. Правило построения последовательности слов

Р = Р0 →…→ Рi →Рi+1 →…→Рn = Q

11. Процедура реализации нормального алгоритма Маркова

1.
2.
3.
В качестве Р0 берется слово Р.
I > 0 слово Рi построено, но процесс не
завершился.
Рi+1 = Рi, если в схеме НА нет формул, с
левыми частями. Процесс построения
последовательности завершен (это
первый критерий останова марковского
алгоритма).

12. Процедура реализации нормального алгоритма Маркова

4. Если в схеме есть формулы с левыми частями,
входящими в Рi то в качестве Рi+1 берется
результат марковской подстановки правой части
первой из таких формул вместо первого
вхождения её левой части в слово Рi.
5. Процесс построения последовательности
является завершившимся, если на данном шаге
была применена формула заключительной
подстановки (это есть второй критерий останова
марковского алгоритма), или продолжающимся
в противном случае.

13. Процедура реализации нормального алгоритма Маркова

Если процесс построения упомянутой
последовательности обрывается, то считается,
что рассматриваемый нормальный марковског
алгоритм применим к слову Р.
Последний член последовательности Рn или Q
называется результатом применения
нормального марковского алгоритма к слову Р.
В результате нормальный марковског алгоритм
перерабатывает исходное слово Р в
результирующее слово Q.

14. Пример

Марковский алгоритм задан
следующей схемой над алфавитом:
А ={а, b}.
Введем алфавит: А = {1, 11, 111}.
If (R mod 3 = 0)
Then (Q = 1) else _Q = ^.

15. Марковский алгоритм имеет следующую схему:

111 → ^
11 → (•) ^
1 → (•) ^
^ → (•) 1

16. Результирующие слова

R = 111 1111→1111→1→^ = Q;
R' = 111 111 →111→^→1 = Q' ;
R'' = 111 11 →11→^ = Q'' ;
R'" = 111 111 11→11 111→11→^ = Q'".

17. СПАСИБО

ЗА
ВНИМАНИЕ