ГЛАВА 6. ЯЗЫКИ СЕТЕЙ ПЕТРИ

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

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

6.1. Мотивы изучения языков сетей Петри

Развитие теории сетей Петри обусловливают две основные причины: 1) описание предлагаемых и существующих систем и 2) анализ систем, моделируемых сетями Петри. Цель анализа сети Петри — определение свойств сети и моделируемой системы. Одно из самых важных свойств системы — это множество действий, которые могут произойти. Множество всех возможных последовательностей действий характеризует систему.

Действия моделируются в сети Петри переходами, осуществление действия — запуском перехода. Последовательности действий моделируются последовательностями переходов. Следовательно, множество разрешаемых последовательностей переходов характеризует сеть Петри и (со степенью корректности моделирования системы сетью Петри) моделирующую систему.

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

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

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

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

Языки сетей Петри могут быть полезны также для анализа сетей Петри. В гл. 4 были разработаны методы определения частных свойств сетей Петри: безопасности, ограниченности, сохранения, активности, достижимости и покрываемости. Хотя установление этих свойств важно (и трудно), они не единственные, которые анализируются в сети Петри. Возможно, окажется необходимым установить корректность моделируемой системы, показав, что ей присущи специфичные свойства. Таким образом, либо для каждого нового свойства нужно разрабатывать новые методы, либо необходимы общие методы анализа сетей Петри.

Исходя из последовательностей действий, возможных в системе, можно поставить множество вопросов. Если определить множество возможных последовательностей действий как язык системы, то система будет анализироваться путем анализа языка. Теперь задачи решаются путем рассмотрения вопроса существования (переведет ли какая-нибудь последовательность действий систему из одного состояния в другое?) или вопроса принадлежности (возможна ли последовательность действий данного вида?). Благодаря этому можно получить общий метод анализа произвольных систем с целью проверки на обладание свойствами, специфичными для них. Риддл [258] занимался исследованиями анализа на основе языка моделируемой системы.

Другое применение языков сетей Петри лежит в области задания и автоматического синтеза сетей Петри. Если задать языком требуемое поведение, то можно будет автоматически синтезировать сеть Петри, обладающую данным языком. Полученную сеть Петри можно использовать в качестве контроллера, гарантирующего, что возможны только указанные последовательности и никакие другие. Для определения разрешаемых последовательностей действий были предложены Е-выражения [163]. На их основе разработаны методы автоматического построения сетей Петри.

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

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