Книжка по сетям Петри, страница 18

С) Т е о р е м а 4П1. Если живая свободная сеть покрывается совокупностью сильно связных автоматных плотнык подсатвй, то она безопасна. До к а з а т е л ь с т в о. Число фишвк в любой изпокрывающих авто. матных подсетей постоянно. Общаа число фишек в свободной сети ограничено сварху суммой фишек во всех покрывающих плотных подсетях. Тогда, по лемме 4.4, ясли сеть жива, то она должна быть безопасной, иначе а ней есть неограниченное место. С) Свободная сеть на рис 4 Ва содержит только один тупик(рырз Рз.

Рч) т.а. все множество мест сети. Тупик содержит размачанную ловушку, совпадающую с самим ту,тиком, позтому эта сеть — живая. Сеть на рис. 4.В,а покрывается разными совокупностями плотных подсетей, например, автоматными подсатями, показанными на рис. 4В.б и в. Однако только подсеть на рис. 43,б является сильно связной сетью. Позтому сеть на рис. 4.В,а на являатся базопасной. В атом лагко убедиться, выполнив. на- пРимеР, послаДоаатальность сРабатываний гч Г, Г, котоРаЯ пРиведет к разметке (0,1,2,1).

ГЛАВА 5 ОБОБЩЕНИЯ СЕТЕЙ ПЕТРИ Анализ языков, порождаемых сетями Патри, показывает, что сати Петри по выразительной мощности, т.а. по способности адекватно моделировать поведение дискретных систем. превосходят такие классы моделей, как конечные автоматы, но все же на обладают "универсальными*' возможно. стажи, так как некоторью классы языков не могут порождатьсн сатямн Патри. Это заставило искать такие обобщения сетей, которые увалнчнвалн бы их выразительную мощность. В этой глава будет рассмотрен рлд модификаций сетей Патри, направлен.

ных на усиление нх моделирующих способностей, и провадано сравнение получаемых классов друг с другом н с классом сетей Петри. $5Л. Счегмгковме автоматы Рассматриваемые ниже обобщения сетей Петри приводят к универсальным моделирующим системам, порождающим ракурсивно-яеречиспимые классы языков, т.е. к системам, равномощным машинам Тьюринга Этот факт проще устанавливается сравнением обобщенных сетей со счетчикоеымо еетомагами, модифнкацнямн машин Минского (12), которые, как известно, равиомощны ммиинам Тьюринга Счетчнковый автомат состоит нз конечного множества счетчиков (Х1 ) 1 СГ' ч. Л), апфаВита И ПРОГРаММЫ аатОМата, Программа автомата представляет собой связный ориентированный граф с одной начальной вершиной без входных дуг, с одной заключительной вершиной без выходных дуг„из остальных вершин выходит одна илн две дуги.

Вершинам приписаны опараторы одного из шести типов (рис. 5.1): а) начальной вершине приписан оператор старт, единственный в щю. грамме, б! заключительной вершине приписан оператор стоп, единственный в программе, в) оператор прибавления единицы кт . ~ хг + 1 может быть приписан вершине с одной выходной дугой, г) оператор печати символа из алфавита автомата: печать а также при. пнсывается вершинами с одной выходной дугой, д! оператор условного вычитания единицы: если х~ чь В то хг .

~ к,— 1 может быть приписан вершинам с двумя выходными дугами, стает е В З)+1 Е ПЕЧатЬ а Г Хг-1 Е е' г' е' е" г' е" Эне. 5.1. г) оператор недетарминироаанного лгрехода ив также ярнписывавгся вершинам с двумя выходными дугами. На рис. 6.1 операторы представлены в некоторой сокращенной форме Матки у выходных дуг указывают вершины (метки операторов), на которью эти дуги заводятся.

Счетчнковый автомат порождает (печатает) слово в елфавите автомата, продвигаясь по программе, меняя значения счетчиков и печатал очередной символ. Движение начинается а начальной вершина. При прохождании оператора х~ . х, + 1 значение счетчика хг увеличивается на 1. При про.

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

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

Если автомат зацикливается при любом возможном варианте выпас)ненни его программы, то он порождает пустой язык. Машине Минского не содержит алфавита, операторов печети и недетарминированного переходе. Поэтомчу она является "числовой" мешиной, задающей накоторую функцию г: 9) - МЯ, где г(лг,,;,лтч) — вектор значений счетчиков х„, . „х„яри остановке машины, лг,,..., тч - на* чальные значения тех же счатчиков. Функция г не определена тогда и только тогда, когда машина зацикливаетсл.

Для любой частично-рекурсивной функции существует задающая ее машине Минского, поэтому майины Минского эквивелентны машинам Тьюринга по своим вычислительным возможностям. Теорема 6.1. Любод рекурсиано лцзечнсгпгмыд язык мохют быть порожден некоторым счетчиков ым автоматом. Д о к а з а т е л ь с т в о. Известно, что любой рекурсивно перечислимый язык может быть взаимно. однозначно отображен в рекурсиано перечнслимое множество целых неотрицательных чисел, причем многими способами, Выберем следующую кодировку К: А' й слов из алфавита А (а~,..., а„) числами: (г Од О. рте~ ЕА, Ъ'аЕА': К(агп) !'ч [я+1) К(а).

Например, кодом двоичного слова 1001 в алфавите (О,1) служит число [2+ 3 (1 + 3 (1 + 3 2))) 68, а кодом строки цифр 123 в алфавите десятичных цифр (1,..., 9 ) служит число (1 + 10 ' (2+ 1О ' 3) ) 321. Кодирующая функция )Г взаимно однозначна, что видно из ее определения, поэтому существует обратная (А|кодирующая) функция 49 гис. в.а К 1: (ч - А'„сопоставляющая числам слова в алфавите А. (Функция К ' является частично определенной, так как функция К отображает множество А ' в (ч, а не на В).) Счетчиковый автомат на рис.

5.2 реализует декодирующую функцию К ', которая является частично-ре. курсивной. Этот автомат имеет два счетчика х и у, он останавливается и печатает слово К '(т), если т является начальным значением счетчикахх и одновременно числом-кодом. В противном случае автомат зацикливается. Таким образом, любой рекурсивно перечислимый язык является образом некоторого рекурсивно перечислимого множества чисел при декодирующей функции К 1, вычис. ляемой некоторым счетчиковьпи ав. томатом. В свою очередь, каждое рекурсивно перечислимое множество чисел является областью значений некоторой частично-рекурсивной функции С которая может быть за. дана машиной Минского. Следовательно, любой рекурсивно перечислимый язык может быть областью значений функции, задаваемой счет.

чиковым автоматом, как показано на рис. 5.3,в. На эпни рисунке фрагмент "х: = г(х)" соответствует подпрограмме, которая представляет собой программу машины М чского (без начального и заключительного операторов), задающей функцию ~ а фрагмент "печать К '(х)" является программой счетчикового автомата на рис. 5.2 (без начального и заключительного операторов) . Наконец, любой рекурсивно перечислимый язык может быть порожден счетчиковым автоматом, программа которого начинается (после оператора старт) недетерминированным переходом, позволяющим получить пРоизвольное значение счетчика х (см. Рис. 5.3, б), и затем совпадает с программой автомате на рис.

5.3, а. Язык, порождаемый автоматом на рис. 5.3,б, совпадает с областью значений суперпозиции Функций К 'Д (::) ОР, ОР (Г 2чать) а ф лис 6.4 7! $ 5.2. Ипгиблторлые сети л сетя с прлорлтетами Вьнле, в главе 2, мы встречались с ситуациями, когда сети Петри модели. ровапи некоторые арифметические операции (% 2.3). Сравнение счетчиковых автоматов с сетями Петри показывает, что пяти нз шести операторов автомата можно сопоставить фрагменты сетей Петри, имитирующие их рт(зету. Например, оператору Старт можно поставить в соответствие начальное место без входных дуг и с единичной разметкой (рис. 5.4,а); оператору стоя — заключительное место без выходных дуг (рис.

5.4,6); оператору печати символа а — переход, помеченный символом а, с одним входным и одним выходным местом (рис 5.4,е!. Оператор недетерминированного перехода моделируется двумя переходами с общим конфликтным входным местом и разными выходными местами (рис. 5.4,г). Опе. ратор прибавления единицы х~ . ~ хг + ! может быть представлен пере. ходом С одним входным и одним выходным местом для моделирования управляющих связей оператора с другими операторами программы и еще одним выходным местом, которое соответствует счетчику хг автома.

та (рис. 5.4, д). Однако оператор условного вычитания единицы не удается промо. делировать средствами сетей Петри. Причина этого состоит в том, что в сети Петри можно заметить (и отметить это срабатыванием некоторого перехода1 тот старт <,—..-0 факт, что место сети изменило разметку с нулевой на нему- с) левую, но нельзя отметить срабатыванием перехода факт ~ Стоп изменения разметкис ненулевой на нулевую.

Таким обре. зом, из двух альтернатив Ц (хг Ф 0 и хг О), содержа. щихся в операторе условного е вычитания единицы, в сети Петри можно представить только одну, первую, но нельзя отразить проверку на ноль, так как сеть не может реаги- 1 ФО А ровать непосредственно на отсутствие фишки в месте (если зто место неограничен. з! РР но, в противном случае это можно сделать косвенным путем). Келлер [541 и Коса- А раю [57! обратили на этот Факт внимание и показали, что сети Петри не могут 41 ! моделировать машины Минс.

кого и Тьюринга. Естественным в этой си- з тузции был шаг, сделанный ФО Р Филином и Аджервалой [16, 171, которые моднфициро- РР Рс" вали сети Петри, введя в них е1 специальные. ингибиторные дуги, осущасталяющие проверку на нулевую разметку, и показали, что получаемое обобщение дает класс сетей (ингибиторные сати), которые могут модалировать счетчнкоаыа автоматы и, следовательно, порождать любые рекурсивно перечмслимые языки.