Нормальный алгоритм Маркова

1.

Нормальный
алгоритм Маркова
Разработал:
студент группы 23 ИСиП
А.Жижикин

2.

Теория нормальных алгоритмов
была разработана советским
математиком А. А. Марковым в
конце 1940-х — начале 1950-х гг. XX в.
А.Марков
Нормальный алгоритм Маркова - это
один из стандартных способов
формального определения понятия
алгоритма.Он был введен А. А.
Марковым в работах по
неразрешимости некоторых проблем
теории ассоциативных вычислений.

3.

Основная идея заключается в том, что
нормальный алгоритм Маркова
представляет собой последовательность
правил замены, которые применяются к
символам входной строки. Эти правила
замены задаются в виде нормальных схем,
которые описывают, какие символы
заменять на какие другие символы.
Нормальные алгоритмы Маркова
используются в ряде ориентированных на
обработку символьной информации языков
программирования, например, в языке
Рефал.

4.

Рассмотрим примеры, в которых демонстрируются
типичные приёмы составления НАМ.
Как и в случае машины Тьюринга, для
сокращения формулировки задач будем
использовать следующие соглашения:
– буквой Р будем обозначать входное слово;
– буквой А будем обозначать алфавит
входного слова, т.е. набор тех символов,
которые и только которые могут входить во
входное слово Р (но в процессе выполнения
НАМ в обрабатываемых словах могут
появляться и другие символы).
Пусть -4 = {а, b} — алфавит. Рассмотрим следующую схему нормального
алгоритма в А:

5.

Всякое слово V в алфавите A,
содержашее хотя бы одно вхождение
буквы а, он перерабатывает в слово.
получаюшееся из V вычеркиванием в
нем самого левого (первого) вхождения
буквы а. Пустое слово он перерабатывает
в пустое. (Алгоритм не применим к таким
словам. которые содержат только букву
b.) Например. ааbаb => аbab, аb => b, аа =>
а, bbаb => bbb, bаbа => bbа.