![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Очень близкой по своей сущности к идеологии МТ, уточняющей понятие алгоритма, является идеология нормальных алгоритмов Маркова. Она отличается от идеологии МТ лишь тем, что в явном виде не оперирует машинными механизмами. Здесь, так же как и в МТ, задается алфавит , который является областью определения некоторого алгоритма U, а также некоторое множество подстановок Р и порядок их применения. Алгоритм Маркова переводит одно слово Q,заданное в виде конечной последовательности букв алфавита А,в новое слово S,состоящее из букв того же алфавита. Говорят, что некоторый алгоритм U применим к слову Q, если оно содержится в области определения алгоритма U,и подстановки выполняются в той же области определения.
Рассмотрим пример задания алгоритма по Маркову. Возьмем алфавит русского языка и будем использовать следующие подстановки:
1. 2.
3.
4.
5. 6.
7.
8.
.
Пусть порядок их применения будет таким:
1) проверить возможность подстановок в порядке возрастания их номеров, и если подстановка возможна, т.е. левая буква подстановки обнаружена в исходном слове, то произвести подстановку, заменив левую букву на правую;
2) если в примененной подстановке имеется символ “!”, то преобразования прекращаются, а если нет, то текущее состояние становится исходным и весь процесс начинается заново;
3) если ни одна подстановка неприменима, то процесс преобразования завершен.
Тогда, например, слово “слон” преобразуется в слово “муха”
“СЛОН”→“СУОН”→“МУОН”→“МУХН”→“МУХА”.
Дата публикования: 2015-01-10; Прочитано: 300 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!