6.3. Определения языков сетей Петри

Основные понятия, используемые для получения регулярного языка по конечному автомату, применимы и к сетям Петри для образования теории языков сетей Петри. В дополнение к сети Петри, определяемой множеством позиций и переходов (которые приблизительно соответствуют множеству состояний и функции переходов автомата), необходимо определить начальное состояние, алфавит и множество заключительных состояний. Задание этого для сети Петри может привести к различным классам языков сетей Петри. Рассмотрим их по порядку.

6.3.1. Начальное состояние

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

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

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

Мы видим теперь, что эти три определения начальных состояний сети Петри в принципе эквивалентны. Отходя от традиции, определим язык сети Петри как начинающийся с отдельной маркировки

6.3.2. Помечение сетей Петри

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

Свободно помеченная сеть Петри — это помеченная сеть Петри, в которой все переходы помечены по-разному (т. е. если то Класс языков свободных сетей Петри является подмножеством класса языков сетей Петри с более общей функцией помечения, в которой не требуются различные метки. Рассматривалась еще более общая функция помечения, допускающая помечение переходов пустым символом, -помеченные переходы не появляются в предложениях языка сети Петри, и, следовательно, их запуск при выполнении сети Петри не фиксируется. Три класса функций помечения (свободные, без и с -переходами) определяют три класса языков сети Петри.

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

6.3.3. Заключительные состояния сети Петри

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

Одно из определений взято по аналогии с соответствующим понятием для автоматов — множество заключительных состояний определяется как конечное множество заключительных маркировок. Этим определением мы вводим класс языков сетей Петри -типа.

Определение 6.1. Язык является языком сети Петри -типа, если существует сеть Петри помечение переходов : начальная маркировка и конечное множество заключительных маркировок такое, что

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

Определение 6.2. Язык является языком сети Петри -типа, если существует сеть Петри помечение : начальная маркировка и конечное множество заключительных маркировок такое, что и существует такое, что

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

Определение 6.3. Язык является языком сети Петри -типа, если существует сеть Петри помечение : и начальная маркировка такая, что определено, но для любого не определено.

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

Определение 6.4. Язык является языком сети Петри -типа, если существует сеть Петри помечение и начальная маркировка такая, что и определено

6.3.4. Классы языков сетей Петри

В дополнение к четырем классам языков сети Петри, основанным на различных заданиях множества заключительных состояний, имеются вариации языков, порожденные различными определениями функции помечения. На рис. 6.1 приведены 12 классов

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

Рис. 6.1. 12 классов языков сетей Петри.

Для задания конкретного языка сети Петри должны быть определены четыре элемента: сеть Петри ; функция помечения : начальная маркировка : множество заключительных маркировок (для языков и -типа). Назовем помеченной сетью Петри для сети Петри С, помечения а, начальной маркировки и множества заключительных состояний Для данной помеченной сети Петри у можно определить 12 языков:

Различные определения языков сетей Петри связывают с данной сетью Петри различные языки. Рассмотрим, например, сеть Петри на рис. 6.2. На сети задана начальная маркировка (1, 0, 0, 0) и каждый переход помечен Если мы определим (одна фишка в позиции языком -типа будет языком -типа — языком -типа — а языком -типа — Языки всех четырех типов для этого примера различны. Данная функция помечения является свободным помечением, но при использовании других функций помечения можно получить и другие языки.

Несмотря на различия в определениях, классы языков сетей Петри тесно связаны. Например, множество свободных помечений включено в множество -помечений, которое является подмножеством множества -помечений. Таким образом,

Кроме того, всякий язык -типа является языком -типа с Поэтому

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

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

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

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

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

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

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

Рассмотренную конструкцию можно также незначительно модифицировать для того, чтобы показать, что обобщение определения языка -типа (допускающее неполное задание заключительных маркировок) не изменяет классов

Рис. 6.3. Сеть Петри, язык -тииа которой совпадает с языком -типа сети Петри, приведенной на рис. 6.2.

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

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

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

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

Вводя не полностью заданные заключительные маркировки, можно показать, что языки -типа являются также языками -типа (за исключением, быть может, свободных языков -типа).

Заключительным состоянием для языка -типа является такое состояние, что никакой из переходов нельзя запустить (т. е. для всех Таким образом, условие, задающее заключительное состояние для языка -типа, в точности противоположно условию, задающему заключительное состояние для языка -типа. (Можно назвать язык -типа обращением языка -типа.) Нетрудно видеть, что такое множество маркировок может быть описано конечным множеством не полностью заданных маркировок (как это сделано в разд. 5.4). Например, условие эквивалентно или Язык -типа (или в более общем случае обращение языка -типа) можно поэтому представить обобщенным (т. е. не полностью заданным) языком -типа и, следовательно, языком -типа. Таким образом,

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

На рис. 6.4 графически представлены соотношения рассмотренных классов языков сетей Петри. Дуга между классами означает включение одним классом языков сетей Петри другого.

Рис. 6.4. Известные соотношения между классами языков сетей Петри. Дуга из класса А в класс В означает, что класс А включает класс В.