Синтез комбинацонных схем и конечных автоматов, сети Петри

Информация - Компьютеры, программирование

Другие материалы по предмету Компьютеры, программирование

Скачать Бесплатно!
Для того чтобы скачать эту работу.
1. Пожалуйста введите слова с картинки:

2. И нажмите на эту кнопку.
закрыть



иводящая к запуску этого перехода.

Реально вводят понятия нескольких уровней активности для конкретных переходов. Переход tj T называется:

а) пассивным (L0- активным), если он никогда не может быть запущен;

б) L1- активным, если он может быть запущен последовательностью переходов из μ0 хотя бы один раз;

в) L2- активным, если для любого числа K существует последовательность запусков переходов из μ0 , при которой данный переход может сработать K и более раз;

г) L3- активным, если он является L2- активным при K → ∞.

  1. Обратимость. Сеть Петри обратима, если для любой маркировки μ

    R(C, μ0) маркировка μ0 достижима из μ.

  2. Покрываемость. Маркировка μ покрываема, если существует другая маркировка μ

    R(C, μ0) такая, что в каждой позиции μ фишек не меньше, чем в позициях маркировки μ.

  3. Устойчивость. Сеть Петри называется устойчивой, если для любых двух разрешённых переходов срабатывание одного из них не приводит к запрещению срабатывания другого.
  4. Существуют два основных метода анализа сетей Петри: матричные и основанные на построении дерева покрываемости.

Первая группа методов основана на матричном представлении маркировок и последовательностей запуска переходов. Для этого определим две матрицы размерности количество позиций количество переходов, связанные со структурой сети. Первая матрица называется матрицей входов:

 

D [i, j] = # (pi , I(tj)), (3.2.16)

 

каждый её элемент равен числу фишек, уходящих из j- й позиции при запуске i- го перехода. Вторая матрица называется матрицей выходов:

 

D + [i, j] = # (pi , O(tj)), (3.2.17)

 

каждый её элемент равен числу фишек, приходящих в j- ю позицию при запуске i- го перехода. Определим единичный вектор e[j] размерности m, содержащий нули во всех позициях кроме той, которая соответствует запускаемому в данный момент переходу. Очевидно, что переход разрешён, если μ ≥ e[j]D . Тогда результат запуска j- го перехода можно описать так:

 

μ = μ + e[j]·D, (3.2.18)

 

где D = (D + D ) матрица изменений. Тогда все сформулированные ранее проблемы сети Петри легко интерпретируются матричными уравнениями вида

 

μ = μ0 + σ·D, (3.2.19)

 

где μ исследуемая маркировка, σ вектор, компоненты которого показывают, сколько раз срабатывает каждый переход.

Хотя данный метод достаточно прост, он не лишён некоторых недостатков. А именно, его применение даёт лишь необходимые условия существования какого- либо свойства, иными словами, может гарантировать лишь его отсутствие, а о присутствии мы сможем говорить с уверенностью, только проанализировав дерево покрываемости (смены) маркировок.

Дерево маркировок сети это связанный граф, в вершинах которого находятся маркировки, которых мы достигли в результате последовательного запуска разрешённых переходов, а на дугах, соединяющих вершины зпускаемые переходы. Путь от корня к каждой маркировке отражает последовательность запусков, приведшую к ней. Корнем дерева является начальная маркировка. При неограниченном накапливании фишек в позиции на дереве образуется петля, а в маркировке на месте, соответствующем зациклившейся позиции, ставится ω символ бесконечно большого числа.

Ясно, что этот метод хотя и требует утомительного перебора всех возможных маркировок сети, но зато по уже готовому дереву достаточно легко анализировать проблемы достижимости, покрываемости, активности, обратимости сети.

Описав поведенческие свойства и методы анализа, можно перейти непосредственно к анализу конкретной сети Петри.

3.3 Расчёты и полученные результаты

Исходная сеть в виде графа:

 

p1 p6

▪ ▪

 

 

t1p4 t4

 

 

p2 p7

 

 

 

t2p5 t5

 

 

p3 p8

 

 

t3 t6

 

 

 

 

 

Рисунок 3.3.1 Исходная сеть Петри

 

Для матричного анализа сети найдём её матрицу изменений.

 

(3.3.1)

 

 

 

 

 

(3.3.2)

 

Матрицу изменений найдём как разность между (3.3.2) и (3.3.1):

 

(3.3.3)

 

Таким образом, получив матрицу изменений, можно записать матричное уравнение смены маркировок вида (3.2.19). Вектор начальной маркировки определим так:

 

s