Мат. лінгвістика 8

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ”ЛЬВІВСЬКА ПОЛІТЕХНІКА”

МЕРЕЖІ ПЕТРІ

МЕТОДИЧНІ ВКАЗІВКИ

до лабораторної роботи №8 з дисципліни «Математична структурна та прикладна лінгвістика»

для студентів напряму «Системи штучного інтелекту»

Затверджено на засіданні кафедри інформаційних

систем та мереж Протокол №14 від 18.05.2012р.

Львів-2012

Мережі Петрі: Методичні вказівки до лабораторної роботи №8 / Укл.: В.А. Висоцька, Ю.В. Нікольський, Т.В. Шестакевич, Ю.М. Щербина. – Львів: Видавництво Національного університету ”Львівська політехніка”, 2012. – 21 с.

Відповідальний за випуск Жежнич П.І., д.т.н., професор.

Рецензенти Берко А.Ю., д.т.н., професор. Чирун Л.В., к.т.н, доцент.

2

Мета роботи: Вивчення методів моделювання систем за допомогою мереж Петрі.

1 ТЕОРЕТИЧНА ЧАСТИНА Поняття мережі Петрі

Мережа Петрі складається з чотирьох елементів: скінченної множини позицій Р = {p1, p2,..., pn}, множини переходів Т = {t1, t2,..., tm},

вхідної функції І:T P, і вихідної функції О:T P. (див. рис. 1)

С= (Р, Т, І, О);

Р= {р1, р2, р3, р4, р5};

Т= {t1, t2, t3, t4};

Рис.1. Приклад аналітичного задання мережі Петрі

Потужність множини Р – |P| = n. Потужність множини Т – |T| = m. Позиція рі є вхідною позицією переходу tі, якщо рі І(tі). Аналогічно,

рі є вихідною позицією переходу tі, якщо рі О(tі). Входи і виходи є переходів є комплектами позицій. Комплект є узагальненням множини. В комплект можуть включатися багаторазово повторені однакові елементи. Прикладом комплекту є O(t1) = {p2, p3, p4, p4}.

Кратність вхідної позиції pi для переходу tj це число появ позиції у вхідному комплекті переходу #(pi, І(tj)). Аналогічно, кратність вихідної позиції pi для переходу tj це число появ позиції у вихідному комплекті

Графи мереж Петрі

Графічним представленням мережі Петрі є двохдольний орієнтований мультиграф. Структура мережі Петрі складається з сукупності позицій і переходів. Відповідно, граф мережі Петрі складається з двох типів вузлів. Кружок позначає позицію а планка | позначає перехід. Отже, оскільки вершини графа можна розділити на дві множини - позиції і переходи то граф є двохдольним.

виходи представлені кратними дугами. Оскільки можуть існувати кратні дуги між вершинами, то маємо мультиграф. Дуги є направлені, тому такий мультиграф є орієнтований.

Таким чином, граф G мережі Петрі це двохдольний орієнтований мультиграф, G = (V,A), де V = {v1, v2,..., vs} - множина вершин, А = {а1, а2,..., аr} - комплект направлених дуг, аі = (vi, vk), де vi, vk V. Множину V можна розбити на дві підмножини що не перетинаються - Р і Т, так що V=P T, P T= і для любої дуги аі(vi, vk) V виконується одна з двох умов: або vi Т, vk Р, або vi Р, vk Т,

Комплект направлених дуг А що відповідають даній мережі Петрі

Двоїстим графом мережі С = (Р, Т, І, О) є граф мережі C = (T, P, І, О), тобто граф в якого позиції і переходи поміняні місцями. Такі графи не представляють практичного інтересу, тому ми їх не розглядаємо.

Маркування мереж Петрі

Маркування - присвоєння певної кількості фішок позиціям мережі Петрі. Фішка це примітивне поняття мереж Петрі (як позиції та переходи). Маркування мережі С = (Р, Т, І, О) є функцією, яка відтворює множину позицій Р в множину невід’ємних цілих чисел N. Маркування можна також

4

подати у вигляді n-мірного вектора = ( 1, 2,..., n), де n = |P|, i N. Вектор визначає для кожної позиції рі кількість фішок в цій позиції і. Частіше застосовується позначення маркування в вигляді функції (рі) = і.

Правила виконання мереж Петрі

Виконання мережі Петрі - це перерозподіл фішок за допомогою запуску переходів. При запуску переходу фішки видаляються з його вхідних позицій і додаються до його вихідних позицій. Перехід може запускатися лише в тому випадку, коли він дозволений. Перехід називається дозволеним, якщо кожна з його вхідних позицій має число фішок не менше ніж число дуг з позиції в перехід. Фішки у вхідній позиції що дозволяють перехід називаються дозволяючими. На рис. 4. фішка в

вхідних позицій і наступним додаванням фішок у кожну з його вихідних позицій по одній фішці для кожної дуги. Перехід tj в маркованій мережі Петрі з маркуванням може бути запущений всякий раз, коли він дозволений. В результаті запуску дозволеного переходу tj утворюється нове маркування , яке визначається таким співвідношенням:

(рі) = (рі) - #(pi, I(tj)) + #(pi, O(tj)).

Приклади запуску переходів мережі Петрі подано на рис. 5. 5

p3

t1 t2

t4 p5

p1 p2

t3

Рис. 5. Маркування отримані в результаті запуску переходів графу зображеного на рис. 4. а) після запуску переходу t4; б) після запуску переходу t1; в) після запуску переходу t3;

Простір станів мережі Петрі

Стан мережі Петрі визначається її маркуванням. Запуск любого з переходів змінює стан мережі шляхом зміни її маркування. Простір станів мережі Петрі, що має n позицій це множина всіх маркувань, тобто Nn. Зміна стану мережі викликана запуском переходу визначається функцією, яка називається функцією наступного стану. Функція наступного станудля мережі Петрі С = (Р, Т, І, О) з маркуванням і переходом tj Р визначена тоді і лише тоді, коли (рі) #(pi, I(tj)) для всіх pi P. Якщо

(рі) визначена, то ( , tj) = , де (рі) = (рі) - #(pi, I(tj)) + #(pi, O(tj)) для всіх рі Р.

Нехай дана мережа Петрі С = (Р, Т, І, О) з початковим маркуванням0. Ця мережа може бути виконана послідовними запусками переходів. Запуск дозволеного переходу tj призведе до утворення нового маркування1 = ( 0, tj). В отриманому маркованому графі можна запустити любий інший дозволений перехід, наприклад tk. Отримуємо маркування 2 = ( 1, tk). Цей процес можна продовжувати до того часу, доки дозволений хоча б один перехід.

При виконанні мережі Петрі отримуємо дві послідовності. Послідовність маркувань ( 0, 1, 2,... ) і послідовність переходів які

6

запускаються (tj1, tj2, tj3,... ). Ці послідовності зв’язані таким співвідношенням:

За допомогою цього співвідношення, маючи структуру мережі Петрі С = (Р, Т, І, О), початкове маркування 0 та послідовність переходів (tj1, tj2, tj3,... ) можемо отримати послідовність ( 0, 1, 2,... ). Зворотній перехід від послідовності маркувань до послідовності переходів можливий у більшості випадків, за виключенням деяких вироджених випадків.

Для мережі Петрі С = (Р, Т, І, О) з маркуванням маркування називається безпосередньо досяжним з , якщо існує перехід tj T, такий, що ( , tj) = , тобто можна отримати з запуском одного з дозволених переходів.

Множина досяжності R(C, ) для мережі Петрі С = (Р, Т, І, О) з маркуванням це найменша множина маркувань, визначених таким чином:

1.R;

2.якщо R, то для всіх = ( , tj), tj T виконується R, тобто якщо якесь маркування належить множині досяжності, то всі досяжні з нього маркування також належать їй.

Часто користуються поняттям розширеної функції наступного стану.

Розширена функція вхідного стану визначається для маркування та послідовності переходів = (tj1, tj2,..., tjn) таким правилом:

= ( , ) = (... ( ( , tj1), tj2)...,tn),

тобто спочатку запускаємо перехід tj1, потім tj2 і так далі, до tjn.

t2

p1 p3

Рис. 6. Мережа Петрі для ілюстрації правил побудови дерева досягальності

7

Рис. 7. Побудова дерева досягальності: а) перший крок; б) другий крок; в) третій крок

Дерево досягальності мережі Петрі є ілюстрацією множини досягальності R(C, ). Оскільки в багатьох випадках множина досягальності є нескінченною, то існують певні правила, які дозволяють відобразити її скінченним деревом досягальності. Для прикладу розглянемо мережу Петрі, зображену на рис. 6. Її початкове маркування

0 = (1,0,0) буде початковою вершиною (коренем) дерева досягальності. В

0 дозволені два переходи - t1 і t2. Нові вершини дерева досягальності будуються для всіх безпосередньо досяжних з 0 маркувань і до них з початкової вершини ведуть дуги помічені переходом що запускається. В результаті запуску t1 отримаємо 11 = (1,0,0), а в результаті запуску t2 отримаємо 12 = (1,0,0). Таким чином, перший крок побудови дерева досягальності буде мати вигляд, зображений на рис. 7,а. Аналогічно здійснюється другий, третій та наступні кроки. Для приведення дерева досягальності до скінченного представлення використовуються такі правила.

Пасивні маркування - тобто маркування в яких немає дозволених переходів є термінальними вершинами дерева досягальності (не мають власних піддерев досягальності).

Якщо отримане маркування вже зустрічалось в дереві досягальності раніше, то такі маркування називають дублюючими вершинами. Розгляд дублюючих вершин зайвий, оскільки отримане піддерево буде аналогічне.

Розглянемо послідовність запусків t1t1t1. Кожен раз, отримане маркування відрізняється від попереднього лише кількістю фішок в p2, яка

8

зростає на одиницю. Таким чином, запускаючи перехід t1 багато раз можна отримати як завгодно велике число фішок в ньому. Тому, якщо запуск переходу збільшує кількість фішок в одній (декількох) позиції залишаючи незмінною кількість фішок в інших, то маркування позиції (позиціїй) в якій кількість фішок збільшилась прийнято позначати символом . Можна розширити це поняття на послідовність переходів , яка збільшує кількість фішок в якійсь позиції, не змінюючи інші позиції. Таким чином, якщо в дереві досягальностей отримуємо маркування, яке є більшим за одне з попередніх (на шляху до кореня) маркувань, то у всіх позиціях що є більші проставляємо символ .

За допомогою цих трьох правил, множину досягальності будь якої мережі Петрі можна подати у вигляді скінченного дерева. Приклад приведеного дерева досягальності для мережі рис. 6 подано на рис. 8.

(1,0,0)

t1 t2

(1, ,0) (0,1,1)

t2 t3

(0, ,1) (0,0,1)

Рис. 8. Приведене дерево досягальності

2 ЛІТЕРАТУРА

Нікольський Ю.В., Пасічник В.В., Щербина Ю.М. Дискретна математика: Підручник. – Львів: "Магнолія Плюс", 2005. – 608с.

3 ЗАВДАННЯ

Розв’язати завдання відповідно до свого порядкового номеру у списку групи. Завдання отримати у викладача. При оформленні лабораторної роботи дотримуватись вимог, які наведені в методичних вказівках. Оцінювання виконаної лабораторної роботи проводиться згідно кількості правильно розв’язаних завдань з відповідного варіанту. Завдання лабораторної роботи мають три рівня складності. Оцінювання виконання завдань першого рівня в п’ятибальній системі відповідає оцінці “задовільно”, другий рівень – “добре”, третій – “відмінно”.

Для всіх варіантів: |P| = n = 5, |T| = m = 4, 0 = {5,5,5,5,5}.

9

26.1,4,3,2,3 ; 4,4,2,3 ; 2,4,2,1 ; 2,2,1 4,1,3 ; 3,3 ; 1,4,1,3 ; 1,4,1,4,2,4,3

Перший рівень

Побудувати граф мережі Петрі згідно з варіантом завдання.

Другий рівень

Скласти функцію визначення можливості запуску переходу мережі Петрі, яка задана множинами (масивами) Р, Т, І, О, М. Аргументом є номер переходу, результатом – 1 перехід дозволений або 0 якщо перехід заборонений. Скласти функцію запуску переходу. Аргументом функції є номер переходу який слід запустити, результатом – змінений масив М і 1 при успішному запуску або не змінений масив М і 0 якщо даний перехід заборонений. За допомогою програми побудувати дерево досягальності заданої мережі Петрі до глибини 3.

Третій рівень

Придумати умову та розв’язати завдання, які б відповідали першому та другому рівням.

10