МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ Національний унiверситет "Львiвська полiтехнiка" Кафедра САПР
ЗВІТ до лабораторної роботи № 9 на тему: Нормальні алгоритми Маркова Виконав: Гр. КН-214 Перевірив: Денисюк П. Ю. Львiв 2007 Мета: Ознайомитись з алгоритмічною системою Маркова, навчитись зображати алгоритм Маркова у вигляді граф-схеми. Алгоритмічна система Маркова заснована на відповідності між словами в абстрактному алфавіті і містить у собі об'єкти подвійної природи: элементарні оператори й елементарні розпізнавачі. Елементарні оператори- оператори алфавіту, послідовне виконання яких реалізує будь-які алгоритми в аналізованій алгоритмічній системі. Елементарні розпізнавачі виконують розпізнавання присутності тих або інших властивостей інформації, що переробляється алгоритмом, а також для зміни (у залежності від результатів розпізнавання) послідовності виконання елементарних операторів. Для визначення множини елементарних операторів і порядка їх виконання у конкретному алгоритмі зручно користуватися особливими орієнтованими графами, які називають граф-схемами алгоритмів. Граф-схема алгоритму (її загальний вигляд наведено на мал. 1) являє собою скінчену множину вузлів, з’єднаних між собою відповідно наступним правилам: ( вузол «вхід» не має вхідних дуг (це позначається як Р+(х) = 0), але має одну вихідну дугу (Р-(х) = 1); ( кожному вузлові, окрім «входу» і «виходу», зіставляється елементарний оператор або розпізнавач; ( у загальному випадку кількість дуг, що входять у вузол граф-схеми, може бути довільною; в окремому випадку (див. мал. 3): - у кожний вузол, якому зіставлено елементарний розпізнавач, входить по дві дуги (Р+(х) = 2) і з кожного такого вузла виходить по дві дуги (Р-(х) = 2); - у кожний вузол, якому зіставлено елементарний оператор, входить по одній дузі (Р+(х) = 1) і з кожного такого вузла виходить по одній дузі (Р-(х) = 1); ( вузол «вихід» має одну вхідну дугу (Р+(х) = 1) і не має вихідних дуг  (Р-(х) = 0); Мал. 3 Алгоритм, визначений граф-схемою, працює таким чином. Вхідне слово надходить на вхід і рухається по напрямкам, зазначеним стрілками. При влученні слова в розпізнавальний вузол здійснюється перевірка умови, зіставленої вузлові. При виконанні умови слово спрямовується в операторний вузол, при невиконанні, - у наступний розпізнавач. Якщо вхідне слово р, яке подано на вхід граф-схеми, проходить через її вузли, перетворюється і кінець-кінцем потрапляє через скінчену кількість кроків на вихід, то враховується, що алгоритм можна застосовувати до слова р (тобто слово р входить в область визначення цього алгоритму). Результатом впливу на слово р буде те слово, що потрапляє до виходу граф-схеми. Якщо ж після подачі слова р на вхід граф-схеми перетворення і прямування слова вздовжо граф-схеми продовжується нескінчено довго, не приводячи на вихід, то враховується, що алгоритм не можна застосовувати до слова р (тобто слово р не входить в область визначення алгоритму). У нормальних алгоритмах в якості элементарного розпізнавача використовується розпізнавач входження, а в якості элементарного оператора - оператор підстановки. Розпізнавач входження перевіряє умову «слово р входить у якості підслова у деяке надане слово q ?». Оператор підстановки заміняє перше зліва входження слова рi у слово q на деяке надане слово р2. Оператор підстановки за звичай задається у вигляді: рi( р2. Наприклад, для слова abcabca застосування підстановки bc(cb через два кроки: ( abcabca ( acbabca ( abcacba ( acbacba призводить до слова acbacba. Послідовність слів p1, p2, ..., pn, одержуваних у процесі реалізації алгоритму, називається дедуктивним ланцюжком. Алгоритм, що задається граф-схемою, яку складено виключно з розпізнавачів входження слів і операторів підстановки, називають узагальненим нормальним алгоритмом. При цьому передбачається, що ...