Расширенные сети петри тест

Тест из 30 вопросов по дисциплине «Теория вычислительных процессов» (Сети Петри применяются исключительно в. Расширение модели сети Петри)

Страницы работы

Фрагмент текста работы

мгновенные б) примитивные в) длительные г) неодновременные д) непримитивные

10. Выберите наиболее правильный ответ а) если сеть Петри безопасна, то она ограничена; б) если сеть Петри ограничена, то она безопасна;

в) безопасность и ограниченность – два независимых свойства сети Петри;

г) безопасность – частный случай более общего свойства (ограниченности);

д) ограниченность – частный случай более общего свойства (безопасности).

11. Выберите наиболее правильный ответ

Чаще всего сети Петри используются для моделирования а) аппаратного обеспечения б) программного обеспечения в) механизмов синхронизации г) процессов конвейерной обработки д) химических реакций е) транспортных потоков

12. Выберите правильный ответ

С помощью сетей Петри нельзя промоделировать задачу а) . о взаимном исключении; б) . о чтении/записи; в) . о чтении/записи с ограниченным количеством процессов чтения; г) . о чтении/записи с не ограниченным количеством процессов чтения; д) . о производителе/потребителе; е) . о нескольких производителях / нескольких потребителях ж) . о производителе/потребителе с ограниченным буфером

13. Выберите правильный ответ

В правильно построенном дереве достижимости сети Петри не может быть . вершины.

а) терминальной б) корневой в) граничной г) дублирующей д) внутренней

14. Выберите неправильные ответы

В с помощью дерева достижимости всегда можно решить задачи сети Петри :

а) безопасность б) ограниченность в) сохранение г) активность д) достижимость е) покрываемость

15. Дополните недостающее слово

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

16. Установите правильную последовательность действий (расположите по порядку)

Для представления системы сетью Петри необходимо:

1. Выявить условия системы 2. Представить события переходами сети Петри 3. Выполнить сеть Петри

4. Составить таблицу связи событий, предусловий и постусловий 5. Представить условия позициями сети Петри

6. Выявить события системы 7. Присвоить начальную маркировку 8. Определить пред- и постусловия

9. Соединить переходы и позиции направленными дугами

Задания на определение зависимости одних явлений от других. В заданиях 17 и 18 Выберите правильный ответ, используя схему

17. Невозможно использовать сети Петри для моделирования параллельных процессов, ПОТОМУ ЧТО запуск перехода ( и соответствующее ему событие) в сети Петри рассматривается как мгновенное событие, занимающее нулевое время.

18. Дерево достижимости сети Петри можно использовать для решения всех задач анализа сети Петри, ПОТОМУ ЧТО оно представляет собой множество достижимости сети Петри.

Источник

Сети Петри. Структура и правила выполнения сетей Петри.

Сети Петри [ править | править код ]

Сети Петри — математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.

Пример работы сети Петри

Сеть Петри представляет собой двудольный ориентированный граф, состоящий из вершин двух типов — позиций и переходов, соединённых между собой дугами. Вершины одного типа не могут быть соединены непосредственно. В позициях могут размещаться метки (маркеры), способные перемещаться по сети.

Событием называют срабатывание перехода, при котором метки из входных позиций этого перехода перемещаются в выходные позиции. События происходят мгновенно, либо разновременно, при выполнении некоторых условий.

Как и стандартные UML диаграммы, BPMN и EPC, сети Петри предоставляют возможность графически иллюстрировать процессы включающие выбор, итерации и одновременное выполнение. Но в отличие от данных стандартов, у сетей Петри четкая математическая формулировка и за ними стоит развитая математическая теория.

==Структура сетей Петри==

Сеть Петри состоит из 4-х элементов:

• множество позиций P,
• множество переходов T,
• входная функция I,
• выходная функция O.

Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.

Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход t_j в множество позиций I(t_j) , называемых входными позициями перехода . Выходная функция O отображает переход p_i в множество позиций O(p_i) , называемых выходными позициями перехода . Структура сети Петри определяется её позициями, переходами, входной и выходной функциями.

Определение

Сеть Петри С является четверкой, C=(P,T,I,O). P=

₁, p₂, . p_i, p_n> — конечное множество позиций, n>=0. T=< t₁, t₂, . t_j, t_m > — конечное множество переходов, m>=0. Множество позиций и множество переходов не пересекаются, то есть пересечение P и T равно пустому множеству. I: T->P ¥ является входной функцией — отображением из переходов в комплекты позиций. O: P ¥ ->T есть выходная функция — отображение из комплектов позиций в переходы.

Произвольный элемент P обозначается символом p_i , i=1, . n, а произвольный элемент T — символом t_j, j=1, . m.

Правила выполнения сетей Петри [ править | править код ]

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

Переход запускается, если он разрешен. Переход называется разрешенным, если каждая из его входных позиций имеет число фишек по крайней мере равное числу дуг из позиции в переход. Фишки во входной позиции, которые разрешают переход, называются его разрешающими фишками. Например, если позиции р1 и р2 служат входами для перехода t1, тогда t1 разрешен, если р1 и р2 имеют хотя бы по одной фишке. Для перехода t3 с входным комплектом позиция р3 должна иметь не менее 3 фишек для разрешения перехода t3.

Определение. Переход

Определение. Переход

Источник

Расширенные сети петри тест

В гл. 3 мы показали, что сети Петри могут быть использованы для моделирования самых различных систем: аппаратного и программного обеспечения вычислительных машин, химических, социальных систем и т.д. Однако это разнообразие примеров лишь показывает, что сети Петри могут адекватно моделировать некоторые системы, но могут существовать системы, которые нельзя должным образом моделировать сетями Петри, т. е. мощность моделирования сетей Петри имеет пределы.

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

В этой главе мы исследуем предложения, которые были сделаны для преодоления двух ограничений сетей Петри: ограничений на мощность моделирования сетей Петри и ограничений на мощность разрешения сетей Петри. Во-первых, рассмотрим некоторые предложения по расширению модели сети Петри. Расширение модели сети Петри должно увеличивать мощность моделирования сетей Петри, но при этом оно может уменьшать их мощность разрешения. Влияние любого расширения на мощность разрешения расширенной модели требует тщательного изучения.

Отметив, что расширение модели сети Петри может приводить к уменьшению мощности разрешения, мы рассмотрим также, как мощность разрешения может быть увеличена посредством ограничения модели сети Петри. Уже предложены различные подклассы моделей сети Петри, которые обусловлены ограничениями на структуру сети Петри. Необходимо исследовать влияние этих ограничений как на мощность моделирования, так и на мощность разрешения.

Такое исследование покажет, как взаимосвязаны мощность моделирования и мощность разрешения, а также укажет границы обеих для модели сети Петри.

7.1. Границы возможностей моделирования с помощью сетей Петри

Исследователи, использовавшие сети Петри для моделирования систем, обнаружили, что возможности моделирования сетями Петри реальных систем ограниченны. Этим объясняется появление тенденции к расширению модели. Имеется несколько типов расширений.

Патил [231] предложил расширить сети Петри путем введения понятия области ограничения. Область ограничения — это множество позиций. Правило запуска модифицируется таким образом, что переход может быть запущен тогда и только тогда, когда в результирующей маркировке не все позиции, входящие в область

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

Рис. 7.1. Переход исключающее ИЛИ. Переход может быть запущен, если одна из позиций имеет фишку.

Ное в своей модели операционной системы [214] ввел другое расширение: переход исключающее ИЛИ (рис. 7.1). В обычных сетях Петри переход запускается, когда все его входы имеют фишки. Такое правило называется логикой поскольку мы должны иметь фишки и в первом входе, и во втором входе, и в третьем входе и т. д. Переход исключающее ИЛИ может запускаться тогда и только тогда, когда точно один из его входов имеет фишки, а все другие фишек не имеют. Следовательно, разрешающее правило состоит в том, чтобы имел фишку или первый, или второй вход (но не оба одновременно). Когда переход запускается, он удаляет фишку только из входа с фишками.

Подобное расширение было использовано Баером в его модели компилятора [23]. Баер ввел понятие переклюнателя (рис. 7.2). Переключатель — это специальный переход со специальным входом, называемым переключающим, и точно двумя выходами (один помечен символом для пустого переключающего входа, а другой помечен символом для непустого переключающего входа). Переключаемый переход запускается, когда он разрешен (независимо от состояния специального переключающего входа). Когда он запускается, фишка помещается в выход, помеченный символом если переключающий вход пуст, или в выход, помеченный символом если переключающий вход не пуст. Таким образом, в зависимости от состояния переключателя запуск переключаемого перехода приведет к одной из двух возможных маркировок. Фишка удаляется из переключающего входа, если он имел ее, поэтому после того, как переключаемый переход запустится, переключающий вход будет пуст.

Рассмотренные расширения сетей Петри были предложены для решения определенных задач, с которыми встретились исследователи

Рис. 7.2. Запуск переключателя. Позиция переключающего входа изображена в виде пятиугольника. а — пустой переключатель; б — полный переключатель.

при попытках моделировать реальные системы. Однако акцент в этих работах сделан на моделирование, а не на теоретическую мощность сети Петри, поэтому в них не рассматривается, были ли эти расширения необходимыми или достаточными для решения общих проблем моделирования. Фактически во всех случаях рассматриваемые сети были безопасными и, следовательно, множество достижимости — конечным, т. е. эти сети представляются конечными автоматами, которые в свою очередь (разд. 3.3.1) легко представляются ординарными сетями Петри. Очевидно, что в описанных случаях были введены не расширения, а некоторые удобства. В разд. 5.3 также показано, что многие расширения ограниченной модели сети Петри, например, допускающие кратные дуги и петли, в действительности являются не расширениями, а средствами, облегчающими моделирование.

Из сказанного выше не становится ясным, что является ограничением (если оно существует) сетей Петри. Ответ на этот вопрос был найден после получения ответа на подобный вопрос и V-операциях Дейкстры над семафорами.

Дейкстра определил свои Р- и V-операции над семафорами для обеспечения синхронизации и связи в системах взаимодействующих процессов [781. Семафор может рассматриваться как целочисленная

переменная, которая принимает только неотрицательные значения. V-операция над семафором увеличивает значение семафора на единицу: наоборот, уменьшает на единицу до тех пор, пока результат не становится равным нулю; при процесс, прежде чем продолжать свою работу, должен ждать момента, когда можно будет уменьшить. Связь между семафорами и сетями Петри была выявлена в разд. 3.4.8.

Поскольку Р- и V-операции были предложены как механизм для решения всех задач синхронизации программ, то естественно возникает вопрос о полноте, т. е. об их способности к решению всех задач координации. Патил в 1971 г. [233] предложил доказательство того, что Р- и V-операции недостаточно мощное средство для решения всех задач координации. Его подход был весьма прост: он сформулировал задачу синхронизации, которая не может быть решена с помощью Р- и V-операций, — это задача о курильщиках сигарет.

Задача о курильщиках сигарет включает (по меньшей мере) четыре процесса, которые моделируют агента и трех курильщиков. Каждый курильщик непрерывно изготавливает сигарету и курит ее. Чтобы сделать сигарету, необходимы три составные части: табак, бумага и спички. Один из курильщиков всегда имеет бумагу, другой — табак, а третий — спички. Агент обладает бесконечными запасами всех трех составных частей. Агент кладет две составные части на стол. Курильщик, имеющий третий недостающий инградиент, может сделать и закурить сигарету, сигнализируя об этом агенту. Тогда агент помещает другие два из трех инградиентов, и цикл повторяется.

Если семафор поставить в соответствие каждой составной части, задача о курильщиках формулируется в терминах семафоров. Семафоры первоначально равны нулю. Агент увеличит два из трех семафоров с помощью V-операций, а затем ждет семафора «сделано». Соответствующий процесс курильщика уменьшает два семафора (с помощью -операций), а затем, произведя действия «сделать сигарету» и «закурить сигарету», увеличивает семафор, указывая «сделано». Задача заключается в том, чтобы разработать программу процессов курильщиков для того, чтобы определить, какой из трех процессов должен действовать в очередной момент. Действия агента фиксированны и не могут быть изменены.

Рис. 7.3 иллюстрирует очевидное «решение». Предположим, агент кладет табак и бумагу Тогда курильщик с бумагой может взять табак а курильщик с табаком может взять бумагу что в результате приводит к тупику.

Патил доказал, что никакая последовательность Р- и V-операций не может корректно решить эту задачу. Это было показано с помощью доказательства того, что все Р- и V-«решения» могут быть промоделированы сетями Петри определенного вида (каждый переход имеет не более двух входов), но что решением является сеть

Рис. 7.3. Задача о курильщиках сигарет.

Петри другого вида, и нет способа преобразовать сеть одного вида в сеть другого вида, не допуская возможности возникновения тупика.

Существовали некоторые сомнения, связанные с решением Патила, — особенно в том, что касается массивов семафоров [230], но тем не менее идея решения верна. следуя работе Патила, получена задача, которая не может быть решена Р- и V-операциями или сетями Петри. То же ограничение мощности моделирования было ранее определено Келлером [150].

Задача, сформулированная в [159, 7], вполне реальна. Предположим, что мы имеем два процесса производителя и два процесса потребителя. Первый процесс: производитель создает элементы данных для первого процесса потребителя а другой производитель для второго потребителя Элементы данных, которые произведены, но еще не использованы, помещаются в буфер: буфер для пары для Передача данных из буферов к потребителям происходит через общий канал. Канал может передавать только по одному элементу за сеанс, причем из любого буфера любому потребителю. Производители просто помещают данные в буфера. Потребители должны координировать свои действия по использованию канала. Управляющий потребитель приказывает каналу передать данные из соответствующего буфера. Все это схематично изображено на рис. 7.4.

Рис. 7.4. Процессы производителя/потребителя с буферизацией и совместно используемым каналом.

Главная проблема, связанная с этой системой, состоит в распределении канала. Пара производитель/потребитель должна иметь приоритет по отношению к на использование канала. А именно, канал никогда не должен передавать элементы данных из буфера потребителю до тех пор, пока буфер не пуст. Это правило приоритета не позволяет системе быть моделируемой сетью Петри.

Идея доказательства относительно проста. Предположим, что мы находимся в состоянии, когда имеется элементов в двух буферах Если сейчас производитель делает перерыв, то все элементы из буфера будут в конце концов переданы производителю и буфер будет пуст. Это позволит переместить элементы из буфера потребителю Таким образом, существует путь из состояния в состояние в котором потребитель может использовать канал. Если сейчас в действительности производитель произведет дополнительно к элементов данных, то мы будем в состоянии а не в состоянии Но из-за нечувствительности условий запусков переходов сетей Петри к числу фишек в позиции последовательность запусков, которая переводила нас из в будет все еще допустимой и переведет нас из состояния к в состояние И поскольку потребитель мог использовать канал в а сеть Петри является не чувствительной к числу фишек

в позиции, то потребитель может использовать канал, несмотря на присутствие элементов в буфере Таким образом, нечувствительность условий запусков переходов сети Петри к числу фишек в позиции не позволяет корректно моделировать эту приоритетную систему.

Более конкретно ограничение на моделирование с помощью сетей Петри состоит в неспособности проверить на наличие точно определенной маркировки в некоторой неограниченной позиции и осуществить действие в зависимости от результатов проверки. Это ограничение общеизвестно как неспособность к проверке на нулевую маркировку в некоторой позиции, и поэтому это свойство известно как проверка на нуль [150]. Сети Петри не могут проверить неограниченную позицию на нуль. [Если позиция ограниченна, то нуль может быть выявлен. Для ограниченной позиции с границей мы можем создать дополнительную позицию такую, что сумма является константой, равной для всех достижимых маркировок. Это позволяет нам проверить, равняется ли нулю, проверяя, равно ли (см. разд. 5.6).]

Источник

Анализ сетей Петри

Моделирование систем сетями Петри, прежде всего, обусловлено необходимостью проведения глубокого исследования их поведения. Для проведения такого исследования необходимы методы анализа свойств самих сетей Петри. Этот подход предполагает сведения исследования свойств реальной системы к анализу определенных свойств моделирующей сети Петри.

4.4.1. Свойства сетей Петри.

Позиция pÎP сети Петри N=(P,Т,I,O) c начальной маркировкой m является k-ограниченной, если m’(p)£k для любой достижимой маркировки m’ÎR(N,m). Позиция называется ограниченной, если она является k-ограниченной для некоторого целого значения k. Сеть Петри ограниченна, если все ее позиции ограниченны.

Позиция pÎP сети Петри N=(P,Т,I,O) c начальной маркировкой m является безопасной, если она является 1 —ограниченной.Сеть Петри безопасна, если безопасны все позиции сети.

Сеть Петри N=(P,Т,I,O) с начальной маркировкой m является сохраняющей, если для любой достижимой маркировки m’ÎR(N,m) справедливо следующее равенство.

Тупик в сети Петри – один или множество переходов, которые не могут быть запущены. Определим для сети Петри N с начальной маркировкой m следующие уровни активности переходов:

Уровень 0: Переход t обладает активностью уровня 0 и называется мёртвым, если он никогда не может быть запущен.

Уровень 1: Переход t обладает активностью уровня 1 и называется потенциально живым, если существует такаяm’ÎR(N,m), что t разрешён в m’.

Уровень 2: Переход t, обладает активностью уровня 2 и называется живым, если для всякой m’ÎR(N,m) переход t является потенциально живым для сети Петри N с начальной маркировкой m’.

Сеть Петри называется живой, если все её переходы являются живыми.

Задача достижимости: Для данной сети Петри с маркировкойm и маркировки m’ определить: m’ÎR(N,m)?

Задача покрываемости:Для данной сети Петри N с начальной маркировкой m и маркировки m’ определить, существует ли такая достижимая маркировка m”ÎR(N,m), что m»>³m’.

(Отношение m»³m’ истинно, если каждый элемент маркировки m» не меньше соответствующего элемента маркировки m’.)

Сети Петри присуще некоторое поведение, которое определяется множеством ее возможных последовательностей запусков переходов или ее множеством достижимых маркировок. Понятие эквивалентности сетей Петри определяется через равенство множеств достижимых маркировок.

Сеть Петри N=(P,Т,I,O) с начальной маркировкой m и сеть Петри N’=(P’,Т’,I’,O’) с начальной маркировкой m’ эквивалентны, если справедливо R(N,m)=R(N’,m’).

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

Более слабым, по сравнению с эквивалентностью, является свойство включения, определение которого совпадает с определением эквивалентности, с точностью до замены = на Í.

4.4.2. Методы анализа.

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

4.4.2.1. Дерево достижимости.

Дерево достижимости представляет все достижимые маркировки сети Петри, а также – все возможные последовательности запусков ее переходов.

Пример 4.4.Частичное дерево достижимости маркированной сети Петри изображено на рисунке 4.10, а, а частичное дерево достижимости для трёх шагов построения имеет вид (рисунок 4.10, б).

Рисунок 4.10 а б

Для сети Петри с бесконечным множеством достижимых маркировок дерево достижимости является бесконечным. Сеть Петри с конечным множеством достижимых маркировок также может иметь бесконечное дерево достижимости (см. пример 4.4). Для превращения бесконечного дерева в полезный инструмент анализа строится его конечное представление. При построении конечного дерева достижимости для обозначения бесконечного множества значений маркировки позиции используется символ w. Также используются следующие ниже операции надw , определяемые для любого постоянного a.

w — а = w; w + а = w; а Алгоритм построения конечного дерева достижимости. Каждая вершина дерева достижимости классифицируется алгоритмом или как граничная вершина, терминальная вершина, дублирующая вершина, или как внутренняя вершина. Алгоритм начинает работу с определения начальной маркировки корнем дерева, и граничной вершиной. Один шаг алгоритма состоит в обработке граничной вершины. Пусть х — граничная вершина, тогда её обработка заключается в следующем:

1. Если в дереве имеется другая вершина y , не являющаяся граничной, и с ней связана та же маркировка, m[x]=m[y], то вершина х становится дублирующей.

2. Если для маркировки m[х] ни один из переходов не разрешен , то x становится терминальной.

3. В противном случае, для всякого перехода tÎT, разрешенного в m[х], создаётся новая вершина z дерева достижимости. Маркировка m[ z], связанная с этой вершиной, определяется для каждой позиции pÎP следующим образом:

3.1. Если m[х](p)=w, то m[z](p)=w.

3.2. Если на пути от корневой вершины к x существует вершина y с m[y] х] посредством запуска перехода t) и m[ y]( p) p), то m[ z]( p)=w. (В этом случае последовательность запусков переходов, ведущая из маркировки m[ y] в маркировку m’, может неограниченно повторяться и неограниченно увеличивать значение маркировки в позиции p.) В противном случае m[z](p)=m’(p).

4. Строится дуга с пометкой t, направленная от вершины x к вершине z. Вершина х становится внутренней, а вершина z – граничной.

Такая обработка алгоритмом граничных вершин продолжается до тех пор, пока все вершины дерева не станут терминальными, дублирующими или внутренними. Затем алгоритм останавливается.

Важнейшим свойством алгоритма построения конечного дерева достижимости является то, что он за конечное число шагов заканчивает работу.

Пример 4.5.Конечное дерево достижимости сети Петри.

Конечное дерево достижимости:

Важнейшим свойством алгоритма построения конечного дерева достижимости является то, что он за конечное число шагов заканчивает работу. Доказательство основано на трёх леммах.

Лемма 4.1. В любом бесконечном направленном дереве, в котором каждая вершина имеет только конечное число непосредственно последующих вершин, существует бесконечный путь, исходящий из корня.

Доказательство. Пусть x 0 корневая вершина. Поскольку имеется только конечное число непосредственно следующих за x 0 вершин, но общее число вершин в дереве бесконечно, по крайней мере, одна из непосредственно следующих за x 0 вершин должна быть корнем бесконечного поддерева. Выберем вершину x 1 непосредственно следующую за x 0 и являющуюся корнем бесконечного поддерева. Теперь одна из непосредственно следующих за ней вершин также является корнем бесконечного поддерева, выберем в качестве такой вершины x 2 . Если продолжать этот процесс бесконечно, то получим бесконечный путь в дереве – x 0, x 1, x 2,…, x n,… .

Лемма 4.2. Всякая бесконечная последовательность неотрицательных целых содержит бесконечную неубывающую последовательность.

Доказательство. Возможны два случая:

1. Если какой-либо элемент последовательности встречается бесконечно часто, то пусть x 0 является таким элементом. Тогда бесконечная подпоследовательность x 0, x 0,…, x 0,… является бесконечной неубывающей подпоследовательностью.

2. Если никакой элемент не встречается бесконечно часто, тогда каждый элемент встречается только конечное число раз. Пусть x 0 — произвольный элемент последовательности. Существует самое большее x 0 целых, неотрицательных и меньших, чем x 0 (0. x 0 — 1), причем каждый из них присутствует в последовательности только конечное число раз. Следовательно, продвигаясь достаточно долго по последовательности, мы должны встретить элемент x 1, x 1 ³ x 0 . Аналогично должен существовать в последовательности x 2, x 2 ³ x 1, и т. д. Это определяет бесконечную неубывающую последовательность x 0, x 1, x 2,…, x n,… .

Таким образом, в обоих случаях бесконечная неубывающая подпоследовательность существует.

Лемма 4.3. Всякая бесконечная последовательность n-векторов над расширенными символом w неотрицательными целыми содержит бесконечную неубывающую подпоследовательность.

Доказательство.Доказываем индукцией по n, где n — размерность векторного пространства.

1. Базовый случай (n=1). Если в последовательности имеется бесконечное число векторов вида , то они образуют бесконечную неубывающую последовательность (так как справедливо w £ w). В противном случае бесконечная последовательность, образованная удалением конечного числа экземпляров , имеет по лемме 4.2 бесконечную неубывающую подпоследовательность.

2. Индуктивное предположение. (Допустим, что лемма верна для n докажем её справедливость для n+1.) Рассмотрим первую координату. Если существует бесконечно много векторов, имеющих. в качестве первой координаты w, тогда выберем эту бесконечную подпоследовательность, которая не убывает (постоянна) по первой координате. Если только конечное число векторов имеют w в качестве первой координаты, то рассмотрим бесконечную последовательность целых, являющихся значениями первых координат. По лемме 4.2 эта последовательность имеет бесконечную неубывающую подпоследовательность. Она определяет бесконечную Последовательность векторов, которые не убывают по своей первой координате.

В любом случае мы имеем последовательность векторов, неубывающих по первой координате. Применим индуктивное предположение к последовательности n-векторов, которая получается в результате отбрасывания первой компоненты n+1-векторов. Полученная таким образом бесконечная подпоследовательность является неубывающей по каждой координате.

Докажем следующую теорему.

Теорема 4.1. Дерево достижимости сети Петри конечно.

Доказательство. Докажем методом от противного. Допустим, что дерево достижимости бесконечно. Тогда по лемме 4.1 (и так как число вершин, следующих за каждой вершиной в дереве, ограничено числом переходов m) в нём имеется бесконечный путь x 0, x 1, x 2,… , исходящий из корня x 0. Тогда m[ x 0], m[ x 1], m[ x 2],… — бесконечная последовательность n-векторов. над NatÈ, а по лемме 4.3 она имеет бесконечную неубывающую подпоследовательность m[ x k0]£m[ x k1]£m[ x k2]£….. . Но по построению дерева достижимости m[ x i]¹m[ x j] (для i¹j), поскольку тогда одна из вершин была бы дублирующей и не имела следующих за собой вершин. Следовательно, это бесконечная строго возрастающая последовательность m[ x k0] x k1] x k2]….. . Но по построению, так как m[ x i] x j] нам следовало бы заменить по крайней мере одну компоненту m[ x j], не являющуюся w, на w в m[ x j]. Таким образом, m[ x k1] имеет по крайней мере одну компоненту, являющуюся w, m[ x k2] имеет по крайней мере две w-компоненты, а m[ x kn] имеет по крайней мере n w-компонент. Поскольку маркировки n-мерные, m[ x kn] имеет во всех компонентах w. Но тогда у m[ x kn+1] не может быть больше m[ x kn]. Пришли к противоречию, что доказывает теорему.

4.4.2.2. Анализ свойств сетей Петри на основе дерева достижимости.

Анализ безопасности и ограниченности. Сеть Петри ограниченна тогда и только тогда, когда символ w отсутствует в ее дереве достижимости.

Присутствие символа w в дереве достижимости (m[ х]( p)=w для некоторой вершины x и позиции p) означает, что для произвольного положительного целого k существует достижимая маркировка со значением в позиции p, большим, чем k (а также бесконечность множества достижимых маркировок). Это, в свою очередь, означает неограниченность позиции p, а следовательно, и самой сети Петри.

Отсутствие символа w в дереве достижимости означает, что множество достижимых маркировок конечно. Следовательно, простым перебором можно найти верхнюю границу, как для каждой позиции в отдельности, так и общую верхнюю границу для всех позиций. Последнее означает ограниченность сети Петри. Если граница для всех позиций равна 1, то сеть Петри безопасна.

Анализ сохранения. Так как дерево достижимости конечно, для каждой маркировки можно вычислить сумму начальной маркировки. Если эта сумма одинакова для каждой достижимой маркировки, то сеть Петри является сохраняющей. Если суммы не равны, сеть не является сохраняющей. Если маркировка некоторой позиции совпадает с w, то эта позиция должна был исключена из рассмотрения.

Анализ покрываемости. Задача покрываемости требуется для заданной маркировки m’ определить, достижима ли маркировка m»³m’. Такая задача решается путём простого перебора вершин дерева достижимости. При этом ищется такая вершина х, что m[ x]³m’. Если такой вершины не существует, то маркировка m’ не является покрываемой. Если она найдена, то m[ x] определяет покрывающую маркировку для m’ Если компонента маркировки m[ x], соответствующая некоторой позиции p совпадает с w, то конкретное её значение может быть вычислено. В этом случае на пути от начальной маркировки к покрывающей маркировке имеется повторяющаяся последовательность переходов, запуск которой увеличивает значение маркировки в позиции p. Число таких повторений должно быть таким, чтобы значение маркировки в позиции p превзошло или сравнялось с m'( p).

Анализ живости. Переход t сети Петри является потенциально живым, тогда и только тогда, когда он метит некоторую дугу в дереве достижимости этой сети.

Ограниченность метода дерева достижимости. Как видно из предыдущего, дерево достижимости можно использовать для решения задач безопасности, ограниченности, сохранения и покрываемости. К сожалению, в общем случае его нельзя использовать для решения задач достижимости и активности, эквивалентности. Решение этих задач ограничено существованием символа w. Символ w означает потерю информации: конкретные количества фишек отбрасываются, учитывается только существование их большого числа.

4.4.2.3. Матричные уравнения.

Другой подход к анализу сетей Петри основан на матричном представлении сетей Петри и решении матричных уравнений. Альтернативным по отношению к определению сети Петри N в виде (P,T,I,O) является определение сети N в виде двух матриц D — и D + , представляющих входную и выходную функции I и O. Пусть каждая из матриц D — и D + имеет m=êTê строк (по одной на переход) и n=êPê столбцов (по одному на позицию).

Матричный вид сети Петри N=(P,T,I,O) задаётся парой ( D — , D + ), где

D — [k,i] = ^ #(p i,t k) – кратность дуги, ведущей из позиции p i в переход t k.

D + [k,i] = # ^ (p i,t k) – кратность дуги, ведущей из перехода t k в позицию p i,

для произвольных 1£k£m, 1£i£n.

Пусть e[k] — m-вектор, k-тый элемент которого равен 1, а остальные равны 0. Переход t k, 1£k£m, в маркировке m разрешен, если m³e[k]× D — . Результатом запуска разрешённого перехода t k в маркировке m является следующая ниже маркировка m’:

где D=( D + — D — ) — составная матрица изменений.

Источник