АЛГОРИТМЫ МАРКОВА
Нормальные алгорифмы Маркова
Нормальные алгорифмы Маркова
Нормальные алгорифмы Маркова
Включение слова в другое слово
Частный случай марковских подстановок
Пример
Определение
Определение
Правило построения последовательности слов
Процедура реализации нормального алгоритма Маркова
Процедура реализации нормального алгоритма Маркова
Процедура реализации нормального алгоритма Маркова
Пример
Марковский алгоритм имеет следующую схему:
Результирующие слова
СПАСИБО
147.50K
Category: mathematicsmathematics

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

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. СПАСИБО

ЗА
ВНИМАНИЕ
English     Русский Rules