Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Нормальные алгоритмы Маркова
|
|
Как и ранее, будем называть алфавитом А всякое непустое конечное множество символов, а сами символы алфавита будем называть буквами.
Словом в алфавите А называется всякая конечная последовательность букв алфавита А. Пустая последовательность букв называется пустым словом и обозначается через .
Если Р обозначает слово Sj1Sj2 … Sjn и Q обозначает слово Sr1Sr2 … Srm, то PQ обозначает объединение Sj1 … Sjn Sr1… Srm. В частности Р = Л = Р. Кроме того, (Р 1 Р 2 ) Р 3 = Р 1 (Р 2 Р 3 ).
Алфавит А называется расширением алфавита В, если В с А. Очевидно, что в этом случае всякое слово в алфавите В является словом в алфавите А.
Алгоритмом в алфавите А называется эффективно вычислимая функция, областью определения которой служит какое-нибудь подмножество множества всех слов в алфавите А и значениями которой являются также слова в алфавите А. Пусть Р есть слово в алфавите А; говорят, что алгоритм U применим к слову Р, если Р содержится в области определения (7, Бели алфавит В является расширением алфавита А, то всякий алгоритм в алфавите В называется алгоритмом над алфавитом А.
Большинство известных алгоритмов можно разбить на некоторые простейшие шаги. Следуя А. А. Маркову, в качестве элементарной операции, на базе которой строятся алгоритмы, выделим подстановку одного слова вместо другого. Бели Р и Q — слова в алфавите А, то выражения Р Q и
Р Q будем называть формулами подстановки в алфавите А. При этом предполагается, что символы стрелка и точка • не являются буквами алфавита А, а каждое слово Р и Q может быть и пустым словом. Формула подстановки Р Q называется простой, а формула подстановки Р •Q называется заключительной.
Пусть Р (•)Q обозначает одну из формул подстановки Р Q или Р • Q. Конечный список формул подстановки в алфавите
Р 1 (•)Q 1
Р 2 (•)Q 2
•••••••••••
Р r (•)Q r
называется схемой алгоритма и порождает следующий алгоритм в алфавите А.
Принято говорить, что слово Т входит в слово Q, если существуют такие (возможно пустые)слова W, V, что Q = WTV.
Пусть Р - слово в алфавите А. Здесь может быть одно из двух:
1. Ни одно из слов Р 1, Р 2 … Р r не входит в слово Р(обозначается: U: Р ).
2. Среди слов Р 1, Р 2 … Р r не существуют такие, которые входят в Р, Пусть m - наименьшее целое число такое, что 1 < т < г, и Рп входит в Р, и R - слово, которое получается, если самое левое вхождение слова Р в слово Р заменить словом Qm. Тот факт, что Р и R находятся в описанном отношении, коротко запишем в виде
U: P-R, (a)
если формула подстановки Рт (•)Qm - простая, или в виде
U: P- • R (b)
если формула Рт (•)Qm - заключительная.
В случае (а) говорят, что алгоритм U просто переводит слово Р в слово R; в случае (b) говорят, что алгоритм U заключительно переводит слово Р в слово R.
Пусть далее, U: P|=R означает, что существует такая последовательность R 1, R 2 … R k слов в алфавите А, что
P = R 0, R = R k, U: Rj\-R j+1для j=1, 2…k-2 и либо U: R k-1| -R kлибо U: R k-1| - • R k (в этом последнем случае вместо U: P|-R пишут U: R | - • R).
Положим теперь U(Р) = R тогда и только тогда, когда либо U: R | - • R либо U: P=R и U: R .
Алгоритм, определенный таким образом, называется нормальным алгоритмом или алгоритмом Маркова.
Работа алгоритма U может быть описана следующим образом. Пусть дано слово Р в алфавите А.Находим первую в схеме алгоритма U формулу подстановки Рm (•) Qmтакую, что Рт входит в Р.Совершаем подстановку словаQm вместо самого левого вхождения слова Рт в слово Р. Пусть R1 - результат такой подстановки. Если Рт (•)Q т - заключительная формула подстановки, то работа алгоритма заканчивается:, и его значением является R1 Если формула подстановки Рт (•)Q т - простая, то применим к R1 тот же поиск, который был только что применен к Р и т.д. Если на конечном этапе будет получено такое слово Ri, что U: Ri , то есть ни одно из слов Р 1, Р 2 … Р r не входит в Ri, то работа алгоритма заканчивается, и Ri будет его значением.
Если описанный процесс на конечном этапе не заканчивается, то говорят, что алгоритм U не применим к слову Р.
Пример 1. Пусть А есть алфавит {b, с }. Рассмотрим
схему
b •
c c
Определяемый этой схемой нормальный алгоритм U перерабатывает всякое слово Р в алфавите А, содержащее хотя бы одно вхождение буквы b, в слово, которое получается вычеркиванием в Р самого левого вхождения буквы b.
Действительно, всякая буква с, находящаяся в слове левее самой левой буквы b, простой подстановкой с с переводится в букву c, а самая левая буква b заключительной подстановкой переводится в пустое слово .
Например, если Р = сcbbc, то Р -Q, где Q = ссbс.
Пустое слово U перерабатывает в само себя.
U не применим к непустым словам, не содержащим вхождения буквы b. Действительно, если слово Р содержит только буквы ct то простой подстановкой с с оно будет перерабатываться в себя, но тогда всегда Р Р, и мы не приходим к заключительной подстановке, т.е. процесс будет продолжаться бесконечно.
Пример 2. Пусть А есть алфавит { а0, а1 … аn }. Рассмотрим схему
I= (а1 )(аi A )
Эта схема определяет нормальный алгоритм U, перерабатывающий всякое слово в алфавите А в пустое слово. Например,
U: а1а2а1а3а0 |-а1а2а1а3 |-а2а1а3|- а2а3|- а3|-
и, наконец, U: . Следовательно, U(а1а2а1а3а0) = .
«Неразрешимые алгоритмические проблемы (обзор)
Переход от интуитивного понятия алгоритма к точному понятию машины Тьюринга позволяет уточнить и вопрос об алгоритмической разрешимости данной массовой проблемы. Теперь этот вопрос можно сформулировать так: существует ли машина Тьюринга, решающая данную массовую проблему или же такой машины не существует?
На этот вопрос теория алгоритмов в ряде случаев дает отрицательный ответ. Один из первых результатов такого типа получен американским математиком Чёрчем в 1936 году. Он касается проблемы распознавания выводимости в математической логике.