Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






Как и ранее, будем называть алфавитом А всякое непустое конечное множество символов, а сами символы алфавита будем называть буквами.

Словом в алфавите А называется всякая конечная последовательность букв алфавита А. Пустая последова­тельность букв называется пустым словом и обознача­ется через .

Если Р обозначает слово 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 году. Он касается проблемы распознавания выводимости в математической логике.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.