ДС18о03-алгорифмы-Маркова (Лекции Северов Часть 1)

Carnegie MellonАлгоритмыМарковаАлгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция 3, 21 сентября, 2018Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.ruhttp://cs.mipt.ru/wp/?page_id=60771Нормальные алгорифмы Маркова1946 г.2ОбозначенияПусть s, s’, a, b, b’, g - некоторые, возможнопустые, строки в алфавите Vпричемs = abg и s’ = ab’gТогда s’ есть результат подстановкиb’ в строку s на место строки b.Такая подстановка может быть задана функциейf(s,a,b,b’)Пример: s=aaaaa, b=aa, b’=b,3Нормальная подстановкаФункция f(s,b,b’) задаёт нормальнуюподстановку, заменяя самое левое вхождениестроки b в строку s на строку b’.Пусть V={a,b,…} – основной алфавит,V’={A, B, …} – вспомогательный, причем VÇV’=Æи b, b’Î(VÈV’)*Тогда b " b’ – это простое правило,а b * b’ – конечное правило подстановки.4Нормальный алгоритм МарковаУпорядоченное множество подстановок видовb " b’ и b * b’Исполнитель, просматривая слово s слева направо,пытается последовательно применить к нему правилаиз множества подстановок.1.

Если удается применить правило вида b " b’, топроцесс повторяется со словом s’;2. Если – вида b * b’ – происходит результативныйостанов.3. Если не удается применить ни одно из правил –останов не результативный (аварийный).5Пример 1: сложение унарных чисел |+ " +|2 +| " |ƒ |* |||||+||+||||||+|||+|||…+||||||+|||…++|||||||||2+|||||||||||||||||||||||||||2ƒ6Пример 2Удалить из непустого слова в алфавите {a,b} первыйсимвол. Пустое слово не менять.a*b*®**a **b *bbbabab -> bbbbabbbbabab ® *bbbabab ® **bbbabab…7Пример 2Удалить из непустого слова в алфавите {a,b} первыйсимвол.

Пустое слово не менять.®**a **b *bbbabab ® *bbbabab ® **bbbabab…*a **b *®*bbbabab ® *bbbabab ® bbabab8Пример 2Удалить из непустого слова в алфавите {a,b} первыйсимвол. Пустое слово не менять.*a **b *®*® * ® **…*a **b ***®*bbbabab ® *bbbabab ® bbabab®*®9Композиция алгоритмов Марковаo Пусть заданы два алгоритма R и S.o Задача: построить алгоритм,который будет выполнять S(R(s)).o Проблема: как заблокировать подстановки Rпосле того, как завершён R и заработал S10Композиция алгоритмов Маркова1.2.3.4.xa®axax®axxh®xhxb®bxn правилn правилn2 правилn правил5.6.7.8.9.bx®bxxh®xhab *SbRan правилn2 правил11Композиция алгоритмов Маркова1.Удвоим алфавит, добавив для каждогосимвола алфавита x его близнеца x2.Добавим еще два символа a и b,которые не входили в исходный алфавит.3.Преобразуем R в Ra заменойправил вида … * z на …®azПреобразуем S в Sb заменой4.1.2.x на xправил вида … * z на …®zb12Пример композиции101+11R: переводдвоичного0|01+1100||1+11в унарное |0 ® 0|| 00||0|+1100|0|||+112 1® 0|000|||||+11ƒ 0®000|||||+0|1*000|||||+0|0|S: суммирование 000|||||+00|||… |||||+|||„ +®||||||||*…22222ƒ„…13Формальная схема|a+aa|a+|+||+|++|bb|||ab®®®®®®®®a|a+a|a+|+||+|++® b|® b|® ||*a11+1|||+|+ ®0|1+1a|||+|a®ab0|0|+1 a|||+|00|||+1 a|||+||0 ® 0|| 00|||+0| a|||+|1 ® 0|0|||+0| a|||+|0 ®|||+0| a||||l ® a|||+|ab||||ab||||ab||||ab||||Вместоab||||l ® b||||14u b1 ® 1bv b0 ® 0bw b *Перевод в унарнуюПеревод в двоичнуюa|| ® |a5|0 ® 0|| 1a| ® 16® 0| 21a® 07®30Сложение® a|8|®4+® b}|®|U15Пример101+111 20|01+111 1|||||+||||||| 400||1+111 2|||||||||||| U…U00||0|+111 1|||||||||||| 800|0|||+111 1000|||||+111 2000|||||+0|11 2000|||||+0|0|1 1000|||||+00|||1 2000|||||+00|||0| 2000|||||+00||0||| 2000|||||+00|0||||| 2000||||| + 000||||||| 3…316Примерa|||||||||||| 5|a|||||||||| 5||a|||||||| 5|||a|||||| 5||||a|||| 5|||||a|| 5||||||a 7||||||0 8a||||||0 5|a||||0 5||a||0 5|||a0 7|||00 8a|||00 5|a|00 6|100 8a|100 61100 }b1100 u1b100 u11b00 v110b0 v1100b w110017Проблема самоприменимостиНевозможно построить НАМ, которыйдля любого другого НАМ выносил бырешение о том, произойдет или нетостанов этого НАМ при его работе надданными, представляющимиописание этого НАМ.18Проблема самоприменимостиСамоприменимый1 a*bпосколькуa*b1b*bНесамоприменимый1 a ® abпосколькуa ® ab 1ab ® ab 1abb ® ab 1…19.