Понятие о нормальных алгоритмах Маркова

Очень близкой по своей сущности к идеологии МТ, уточняющей понятие алгоритма, является идеология нормальных алгоритмов Маркова. Она отличается от идеологии МТ лишь тем, что в явном виде не оперирует машинными механизмами. Здесь, так же как и в МТ, задается алфавит , который является областью определения некоторого алгоритма U, а также некоторое множество подстановок Р и порядок их применения. Алгоритм Маркова переводит одно слово Q,заданное в виде конечной последовательности букв алфавита А,в новое слово S,состоящее из букв того же алфавита. Говорят, что некоторый алгоритм U применим к слову Q, если оно содержится в области определения алгоритма U,и подстановки выполняются в той же области определения.

Рассмотрим пример задания алгоритма по Маркову. Возьмем алфавит русского языка и будем использовать следующие подстановки:

1. 2. 3. 4.

5. 6. 7. 8. .

Пусть порядок их применения будет таким:

1) проверить возможность подстановок в порядке возрастания их номеров, и если подстановка возможна, т.е. левая буква подстановки обнаружена в исходном слове, то произвести подстановку, заменив левую букву на правую;

2) если в примененной подстановке имеется символ “!”, то преобразования прекращаются, а если нет, то текущее состояние становится исходным и весь процесс начинается заново;

3) если ни одна подстановка неприменима, то процесс преобразования завершен.

Тогда, например, слово “слон” преобразуется в слово “муха”

“СЛОН”→“СУОН”→“МУОН”→“МУХН”→“МУХА”.