6.4. Свойства языков сетей Петри

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

Очевидно, что все 12 классов языков исследовать в этой книге невозможно, поэтому мы ограничимся рассмотрением здесь только одного класса языков сетей Петри, а именно языков -типа. Основными причинами такого решения являются ограниченность объема монографии и то, что этот язык уже исследовался в литературе [236, 115]. Некоторые результаты были получены Хэком [115] и для префиксных языков (т. е. -типа) и будут представлены в нашем заключении. Языки и -типа были определены, но никакой работы по их развитию не проводилось. Напомним, что класс языков -типа включает классы языков и -типа. Таким образом, языки -типа в некотором смысле образуют наибольший класс языков сетей Петри, и поэтому понятно, почему они исследовались первыми.

При изучении свойств языков сетей Петри -типа обратимся к двум аспектам. Сначала представим свойства замкнутости сетей Петри]) по отношению к некоторым обычным операциям:

конкатенации, объединению, параллельной композиции, пересечению, обращению, дополнению, бесконечной конкатенации и подстановке. Затем рассмотрим взаимосвязь между языками сетей Петри и классическими формальными языками: регулярными, контекстно-свободными, контекстно-связанными и типа 0. Это позволит оценить силу и ограниченность языков сетей Петри -типа), а также покажет, как можно исследовать другие классы языков сетей Петри.

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

Определение 6.5. Помеченная сеть Петри с языком имеющая стандартный вид, удовлетворяет следующим условиям:

1. Начальная маркировка состоит точно из одной фишки в начальной позиции и не имеет фишек в других позициях.

2. Существует позиция такая, что

в) не определено для всех имеющих в фишку (т. е.

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

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

Теорема 6.1. Всякая сеть Петри эквивалентна сети Петри стандартного вида.

Доказательство. Доказательство проведем с помощью

Рис. 6.5. Приведение сети Петри к стандартному виду. Выполнение этой сети совпадает с выполнением первоначальной сети.

вспомогательного построения. Пусть помеченная сеть Петри с Покажем, как построить эквивалентную сеть стандартного вида (рис. 6.5).

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

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

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

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

1. Вводим в

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

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

Помечение определяется следующим образом:

Любая строка а порождается по определению последовательностью такой, что По построению

Рис. 6.6. Сеть Петри нестандартного вида. Позиция является и начальной, и заключительной.

Рис. 6.7. Сеть Петри стандартного вида, эквивалентная сети Петри, приведенной на рис. 6.6. t

поэтому а Следовательно, и сети эквивалентны. Сеть у имеет по построению стандартный вид.

На рис. 6.6 приведена простая сеть Петри, не имеющая стандартного вида. Применение к этой сети Петри конструкции из доказательства приводит к сети Петри, показанной на рис. 6.7.