О языках вложенных рекурсивных сетей Петри

Размещено на http://www.allbest.ru/

О языках вложенных рекурсивных сетей Петри

Владимир А. Башкин,

Ирина А. Ломазова

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

Формализмы, основанные на сетях Петри ([Котов, 86]), являются удобным инструментом для моделирования и анализа различных параллельных и распределенных систем управления. В данной работе исследуются языковые свойства так называемых вложенных рекурсивных сетей Петри ([Lomazova, 99]), которые позволяют моделировать системы с модульной и динамической структурой. Эта модель представляет собой дальнейшее развитие концепции вложенных сетей Петри [Ломазова, 99]. Во вложенных сетях в качестве фишек выступают обычные сети Петри, которые имеют автономное поведение и могут взаимодействовать с системной сетью. Это позволяет интуитивно ясно моделировать иерархические системы с динамической структурой. Рекурсивные вложенные сети Петри - обобщение вложенных сетей, в котором сеть может порождать в качестве элемента (фишки) свою собственную копию, что снимает ограничения на глубину вложенности. Рекурсивные сети оказались более удобными для моделирования систем, имеющих рекурсивную природу. В частности, известно [Jantzen, 1987], что такой фундаментальный класс формальных систем, как класс контекстно-свободных языков не сравним с классом языков, порождаемых обыкновенными сетями Петри. В то же время существует довольно простой способ моделирования рекурсивными сетями произвольного КС-языка. В данной работе приводится алгоритм построения рекурсивной вложенной сети Петри, порождающей произвольный КС-язык в качестве тупикового.

Рекурсивные вложенные сети

Определение 1. Сетью будем называть набор N=(P,T,F), где P - конечное множество позиций, T - конечное множество переходов, PT=Ш; F(PЧT)(PЧT) - функция инцидентности.

Мультимножество m над непустым множеством S - это функция m:SN, где N - множество неотрицательных целых чисел. Числа {m(s)| sS} называются коэффициентами мультимножества, m(s) определяет число экземпляров элемента s. Множество всех мультимножеств над множеством S будем обозначать как S_MS.

Определение 2. Для произвольного элемента сети xPT через x и x обозначим мультимножества его входных и выходных элементов, такие что y(PT) x(y)=F(y,x), х(y)=F(x,y).

Определение 3. Пусть N=(P,T,F) - сеть, S - произвольное множество. Разметка M в сети N над множеством S есть функция из P в S_MS, ставящая в соответствие каждой позиции мультимножество над S. Размеченная сеть есть сеть вместе с некоторой разметкой, называемой начальной разметкой сети.

В этом определении элементы S (фишки) могут быть сложными объектами, например, сетями.

Пусть X - множество имен переменных и констант, интерпретируемых над некоторыми множествами. Определим язык Expr(X) выражений над X как множество выражений, построенных из элементов X при помощи операций объединения и умножения на натуральное число.

Через Var(expr) обозначим множество переменных, содержащихся в выражении expr.

Определение 4.

Для переменной xX, xExpr(X) и Var(x)=x;

Для константы xX, xExpr(X) и Var(x)=;

Если e₁,e₂Expr(X), то Var(e₁+e₂)=Var(e₁)Var(e₂).

Теперь мы переходим к определению рекурсивной вложенной сети Петри.

Определение 5. Пусть V - множество переменных, C - множество имен констант. Пусть = {l₁, l₂, …} - множество меток. Для каждой метки l определим парную ей метку , такую что =def l и множества и = def {| l} не пересекаются.

Структура рекурсивной вложенной сети Петри есть конечное множество сетей N₁=(P₁,T₁,F₁), … , N_k=(P_k,T_k,F_k), k1 (сеть N₁ называется системной, а сети N₂, … , N_k - элементными) такое, что для каждой сети N_i , i=1, … ,k:

входные дуги переходов помечены выражениями из Expr(V), таким образом, что в любом выражении eExpr(V) имеется не более одного вхождения каждой переменной vV и для каждого перехода tT_i, для p,p't (pp') Var(E(p,t))Var(E(p',t))=, где E(p,t) обозначает выражение, которым помечена дуга (p,t);

выходные дуги переходов помечены выражениями из Expr(VC);

некоторые переходы в сети N_i помечены метками из .

Определим рекурсивно множество MarkedNets всех размеченных сетей из :

Обычную черную фишку будем рассматривать как маркированную сеть с пустой структурой;

MarkedNets={(N_i, f) | N_i , f: P_iMarkedNets_MS}.

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

Определение 6. Рекурсивной вложенной сетью Петри (RNP-сетью) будем называть структуру , в которой каждой константе cC поставлена в соответствие некоторая размеченная сеть из MarkedNets.

Разметкой RNP-сети называется разметка ее системной сети.

Размеченная RNP-сеть RNPN есть RNP-сеть вместе с некоторой ее разметкой (с конечным числом уровней вложенности), называемой начальной разметкой сети.

Определение 7. Пусть N_i=(P_i, T_i, F_i) - сеть в рекурсивной сети RNPN.

Означивание перехода tT_i есть функция b, приписывающая каждой свободной переменной v из выражений на инцидентных t дугах значение b(v) из множества MarkedNets.

Означенный переход есть пара Y=(t,b), где t - переход и b - означивание t.

Означенный переход Y=(t,b) является активным при разметке M в N_i, если pt E(p,t)(b)M(p).

Активный при разметке M означенный переход Y=(t,b) может сработать с результирующей разметкой M' (обозначается M [Y M'), где M'(p)=(M(p)\E(p,t)(b))E(t,p)(b) для всех pP.

Для срабатывания M [Y означенного перехода M'Y=(t,b) мультимножество E(p,t)(b) размеченных сетей будем называть набором вовлеченных в это срабатывание элементных сетей.

Определим теперь шаг срабатывания в сети RNPN.

Определение 8. Пусть RNPN - RNP-сеть. Шаг в RNPN есть один из следующих двух видов срабатываний:

срабатывание непомеченного перехода в сети N_i (при некотором означивании), не меняющее разметки ни в сетях, являющихся элементами (фишками) N_i, ни в сети, в которой данная сеть N_i сама является фишкой (если таковая имеется), называется автономным шагом;

одновременное срабатывание перехода t с меткой l₁ в сети N_i и переходов t_k с меткой l₂, такой что = l₁, во всех непустых сетях из набора вовлеченных в это срабатывание элементных сетей (по одному переходу в каждой сети N_k) в соответствие с некоторым означиванием. Такой шаг называется синхронным.

Разметка M' достижима (непосредственно) от разметки M, что обозначается как MM', если существует шаг в RNPN, ведущий от M к M'.

Исполнение RNP-сети RNPN есть последовательность разметок M₀M₁M₂… , достижимых от начальной разметки M₀.

3. Языки, порождаемые сетью

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

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

Определение 9. Пусть A - некоторый конечный алфавит. Назовем RNP-сеть помеченной, если некоторые переходы в сетях N₁, … , N_k помечены символами из A.

Каждый автономный шаг M₁M₂ помеченной сети порождает символ из A, которым помечен сработавший переход, или пустой символ, если данный переход непомечен. Будем считать, что синхронный шаг может сработать, только если все составляющие его переходы помечены одним и тем же символом из A (или все непомечены). Таким образом, любое исполнение M₀M₁M₂… порождает некоторое слово из A*.

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

Напомним классическое определение контекстно-свободных языков:

Формальная порождающая грамматика G - это формальная система, определяемая четверкой объектов G=V,W,S,R, где V - алфавит терминальных (основных) символов; W - алфавит нетерминальных (вспомогательных) символов; VW=; R - конечное множество правил вывода вида , где и - цепочки в алфавите VW; S - начальный символ (аксиома грамматики).

Языком L(G), порождаемым грамматикой G, называется множество всех цепочек в терминальном алфавите V, выводимых из S в соответствие с правилами R.

Грамматика называется контекстно-свободной (КС-грамматикой), если все ее правила вывода имеют вид A, где AW, (VW)*.

3. Рекурсивные вложенные сети, порождающие КС-языки

Определим несколько преобразований над простейшими рекурсивными сетями.

Рис. 1. Сеть-цепочка

Цепочкой назовем сеть N=(P,T,F) вида:

В сети N выделяются две позиции - головная позиция head(N) и хвостовая позиция tail(N), и один головной переход t_head(N).

Определим следующие две операции над цепочками:

Конкатенация. Пусть N₁=(P₁,T₁,F₁) и N₂=(P₂,T₂,F₂) - цепочки, тогда

N₁.N₂=(P₁P₂\ {head(N₂)}, T₁T₂, F₁ (F₂\ {( head(N₂),t_head(N₂) )}) { (tail(N₁), t_head(N₂))} ).

Склеивание головных позиций. Пусть N₁=(P₁,T₁,F₁), … , N_k=(P_k,T_k,F_k) - цепочки, тогда

Link(N_i)=((P_i\{head(N_i)}){p}, T_i, ( F_i \{(head(N_i),t_head(N_i))} {(p,t_head(N_i))}) ).

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

Введем также три шаблона элементарных рекурсивных сетей, которые будут играть роль атомарных структур, из которых будет строиться итоговая сеть (Рис.3). На рисунке метки из проставлены внутри переходов, метки из A - над переходами. Эти шаблоны имеют структуру цепочки, поэтому к ним применимы операции конкатенации и склеивания.

Рис. 2. Операции над сетями

Теорема. Для любой КС-грамматики G существует помеченная RN

Рис. 3. Шаблоны

P-сеть, порождающая L(G) в качестве тупикового языка.

Доказательство

В качестве доказательства приведем алгоритм построения RNP-сети по произвольной КС-грамматике G=V,W,S,R:

Для каждого правила вывода R_iR построим соответствующую ему сеть-цепочку N(R_i):

Пусть R_i: T. Введем переменную :=. N(R_i):=({p},,).

Если длина не равна 0, то возможны два случая:

=T'', где T'W, '(VW)*. Тогда N(R_i):=Term(NT').N(R_i), :=', и возвращаемся на шаг 2'.

=a', где aV, '(VW)*. Тогда N(R_i):=NoTerm(a).N(R_i), :=', и возвращаемся на шаг 2'.

N(R_i):=N(R_i).Empty.

Обозначим IT ={i|R_iR & R_i=T}. Построим для каждого TW сеть NT=LinkiI_T(N(R_i)).

Искомая помеченная RNP-сеть RNPN есть сеть, структура которой состоит из системной сети NI и множества элементных сетей {NT}TW. Каждой константе на дугах сопоставлена сеть с соответствующим именем и одной черной фишкой в головной позиции в качестве разметки. Начальная разметка состоит из одной черной фишки в головной позиции системной сети NI. Lab={l}, A=V.

Для конечных грамматик данный алгоритм конечен, так как, во-первых, R конечно, поэтому конечно число шагов 1 и 2, и, во-вторых, на каждом шаге вида 2' происходит уменьшение рассматриваемой строки, а длина строк в R также конечна.

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

Вообще, сработать всегда может только переход во внутреннем слое (возможно, синхронно с переходом в соседнем слое, причем при этом самый внутренний слой просто исчезнет), поскольку, в соответствии со структурой сети NoTerm, содержащая объект сеть всегда дожидается его исчезновения, прежде чем сможет сработать сама. Правильная вложенность объектов друг в друга (в соответствии с правилами вывода) позволяет в этом случае гарантировать правильность порождения языка L(G).

Приведенные результаты показывают, насколько существенно может увеличиться выразительная мощность формальных систем при введении понятия рекурсии. Средствами обыкновенных сетей Петри невозможно моделирование КС-языков, поскольку объем их множеств достижимости растет медленнее, чем экспоненциально от длины срабатывания [Jantzen 1987], тогда как количество слов длины n, составленных из алфавита объема k, равно kⁿ. Обыкновенными сетями Петри невозможно моделировать даже довольно простые КС-языки, например {ww^-1 | w{a,b}*} - правильно вложенные последовательности скобок двух видов. Рекурсивные сети в этом смысле более гибкий инструмент, поскольку их свойства позволяют адекватно отражать рекурсивность, заложенную в формальных грамматиках. В то же время, несмотря на значительное увеличение выразительной мощности по сравнению с обыкновенными сетями Петри, есть основания предполагать ([Lomazova et al, 99]), что они менее мощны, чем универсальные системы (машины Тьюринга), что делает возможным их анализ.

Литература

[Котов, 1984] Котов В.Е. Сети Петри. - М.: Наука, 1984.

[Ломазова, 99] Ломазова И.А. Моделирование мультиагентных динамических систем вложенными сетями Петри - Программные системы: Теоретические основы и приложения, с.143-156. - М.: Наука. Физматлит, 1999.

[Jantzen 1987] Jantzen M. Language Theory of Petri Nets - LNCS,254 (1987).

[Lomazova, 99] Lomazova I.A. Nested Petri nets - a Formalism for Specification of Multi-Agent Distributed Systems - Proceedings of the Concurrency Specification and Programming (CS&P'99) Workshop, Warsaw, Poland, 28-30 September 1999, p.127-140 - Warsaw, 1999.

[Lomazova et al, 99] Lomazova I.& Schnoebelen Ph.. Some decidability results for nested Petri nets - Perspectives of System Informatics (Proceedings of Andrei Ershov Third International Conference) , p.143-148 - Novosibirsk: A.P.Ershov Institute of Informatic Systems, 1999.

Размещено на Allbest.ru