Помеченная сеть

Cтраница 2

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

Чтобы установить справедливость соотношения 6), достаточно убедиться, что в любую помеченную сеть Петри можно ввести дополнительные Л - переходы таким образом, чтобы нулевая разметка была достижима от любой разметки сети и префиксные языки новой и старой сети совпадали. Для этого достаточно для каждого места заданной сети ввести свой X-переход без выходных дуг, который изымает при своем срабатывании по одной фишке из этого места. Новые Л - переходы могут срабатывать в любое время, уменьшая разметку сети. [17]

Покажем теперь методом от противного, что язык L не может быть префиксным языком ни одной помеченной сети Петри без Х - переходов. С этой целью допустим существование такой сети ck местами. Аг местах сети при начальной разметке, а т - максимальное число фишек, которое может добавиться в сети при срабатывании какого-то перехода. Тогда после л срабатываний любых переходов сети последняя содержит не более чем т0 тп фишек. [18]

Петри включает терминальные языки всех помеченных сетей, образованных из сетей класса Jf, в том числе помеченных сетей с Х - переходами. [19]

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

Эта сеть порождает язык, который, как было установлено в доказательстве теоремы 3.6, не порождается никакой помеченной сетью Петри. [21]

Доказательство, а) Любой конечный автомат, порождающий язык L над алфавитом / 4, можно легко преобразовать в помеченную сеть без Х - переходов, порождающую такой же терминальный язык, следующим простым образом. Каждому состоянию qt G Q автомата сопоставляется место PI в сети Петри, каждая дуга пересекается переходом и этот переход помечается тем же символом из А, что и эта дуга. Начальная разметка задается так, что единственную фишку содержит место, соответствующее начальному состоянию, все остальные места имеют нулевую разметку. В качестве терминальной разметки берется разметка, при которой имеет фишку только место, соответствующее заключительному состоянию. [22]

На рис. 3.5 6 показана помеченная сеть, построенная таким образом по автомату на рис. 3.5 а. Простой анализ способа построения помеченной сети по конечному автомату убеждает в том, что язык, допускаемый автоматом, совпадает с терминальным языком построенной сети. [23]

С учетом теоремы 3.1 1 достаточно показать, что проблема пустоты терминальных языков сводима к проблеме их конечности. Пусть порождающая заданный терминальный язык помеченная сеть представлена в стандартной форме. Новый переход не влияет на достижимость терминальной нулевой разметки. Если для исходной сети существует терминальная помечающая последовательность ( для Mf 0), то тогда в модифицированной сети существует сколь угодно длинная терминальная помечающая последовательность, получаемая за счет того, что сеть начинает рг чггу с произвольно большого числа срабатываний добавленного перехода. Поэтому терминальный язык модифицированной сети бесконечен в том и только том случае, если язык исходной сети не пуст. [24]

Покажем, например, что иерархическую сеть можно трансформировать в сеть с приоритетами, которая Х - эквивалентна исходной сети в следующем смысле. Сравниваются свободный язык иерархической сети и язык помеченной сети с приоритетами ( или сети другого типа), причем помечающая функция для последней сети имеет вид 2 ( f) t или Z ( f) X, т.е. помечающая функция является частичной. Другими словами, так помеченная сеть отличается от непомеченной лишь наличием дополнительных Х - переходов, символы которых не используются при порождении нзыка сети. [25]

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

Другими словами, старые переходы сохраняют в ординарной сети помечающие символы ( в том числе символы X, если исходная сеть содержит Х - переходы), а все дополнительные переходы становятся Х - переходами. Из соотношения между свободными языками исходной и построенной сетей и между помечающими функциями 2 и 2 следует, что как префиксные, так и терминальные языки этих сетей совпадают. Предлагаемое преобразование приводит в общем случае к тому, что помеченная сеть без Х - переходов преобразуется в ординарную помеченную сеть, содержащую Х - переходы. Теорема 3.3 говорит о невозможности избавиться в общем случае от Х - переходов, и, следовательно, не ясно, можно ли помеченную сеть Петри без Х - переходов преобразовать в ординарную помеченную сеть без Х - переходов. Однако в другой работе [44] Жак предложил новое преобразование, результатом применения которого к сети без Х - переходов является ординарная помеченная сеть ( в общем случае также с Х - переходами), которую можно преобразовать в эквивалентную сеть без Х - переходов. [28]

Страницы: 1 2 3