Обработка данных

Модель процесса обработки данных. Конечные автоматы

Важную роль в процессе обработки данных (поимо самих данных, подвергаемых обработке) играет активная составляющая процесса - некоторая сущность, выполняющая обработку. Таким обработчиком, или преобразователем данных, могут быть как люди, так и некоторые устройства. Важнейшие характеристики процесса обработки данных зависят от того, как функционирует преобразователь. Поэтому создание и исследование различных моделей обработки имеет важное теоретическое и практическое значение. Одной из таких моделей является понятие конечного автомата [32], [36]. Конечный автомат можно охарактеризовать как устройство, имеющее входной и выходной каналы; в процессе функционирования на каналы поступают дискретные порции данных (буквы алфавита). Автомат может находиться в одном из конечного числа внутренних состояний. По определенному закону (в зависимости от состояния автомата и входных данных) осуществляется преобразование входной порции данных в выходные данные и смена состояния автомата. Формально конечный автомат определяется следующим образом.

Определение. Конечным автоматом называется набор из пяти объектов $$\{A,B,S, \varphi, \psi \}$$, в котором:

$$A =\{a_1, a_2, \dots,a_n\}$$ - входной алфавит;

$$B=\{b_1, b_2, \dots, b_m\}$$ - выходной алфавит);

$$S =\{s_1, s_2, \dots,s_r\}$$ - множество внутренних состояний автомата;

$$\varphi :S \times A \to S$$- функция перехода в следующее состояние (переходная функция);

$$\psi : S \times A\to B$$ - функция выхода (выходная функция).

Таким образом, конечный автомат математически описывается тремя множествами и двумя функциями. Функционирование автомата состоит в том, что он "считывает" последовательность входных символов ("программу") и затем "выпечатывает" последовательность выходных символов. Действие происходит последовательно. Конечный автомат, находящийся сначала во внутреннем состоянии $$s_j$$, считывает первый входной символ $$a_k$$. Функция $$\psi$$ принимает на паре $$(s_j, a_k)$$ значение $$b_q$$, которое выпечатывается в качестве первого выходного символа. Функция $$\varphi$$ принимает на паре $$(s_j, a_k)$$ значение $$s_i$$, которое является следующим внутренним состоянием автомата. Затем автомат считывает новый входной символ, выпечатывает выходной, переходит в следующее состояние и т.д., пока не кончится программа.

На рис.8.1 дан удобный способ представления последовательных тактов работы автомата.

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

В нашем определении подразумевается, что функции $$\varphi$$ и $$\psi$$ в описа-нии автомата $$М$$ всюду определены: каждый элемент $$S \times A$$ задает их значения. Такое описание автомата является полным. Коль скоро задано начальное состояние такого автомата, он способен считывать любую программу и выдавать однозначно определенную цепочку символов. Иными словами, существует функция, которая ставит в соответствие любому начальному состоянию $$s$$ и любой последовательности входных символов вполне определенную последовательность выходных символов.

(рис 8.1) Конечный автомат

Пусть $$a(i) $$ - полученный на вход автомата знак на $$i$$-м шаге, $$s(i) $$ - состояние, в котором находился автомат на $$i$$-м шаге, а $$b(i) $$ - знак, который вырабатывает автомат на $$i$$ -м шаге в качестве выходного значения. Работа автомата, то есть переход из состояния в состояние и появление выходных знаков, с использованием функций $$\varphi$$ и $$\psi$$ может быть описано выражениями

$$s(i+1)=\varphi (s(i), a(i))$$ $$b(i)=\psi (s(i), a(i))$$

Поскольку множества $$S$$ и $$A$$ конечны, функции, заданные на их декартовом произведении $$SA$$, удобно задавать табличным способом. На рис.8.2 показан общий вид таблиц, задающих переходную функцию $$\varphi$$ и выходную функцию $$\psi$$ конечного автомата.

Рассмотрим пример конечного автомата, у которого $$A=B=\{0, 1\}$$, имеется два состояния $$S=\{s_1, s_2\}$$, а функции $$\varphi$$ и $$\psi$$ задаются таблицами

$$\varphi$$	0	1
$$s_1$$	$$s_1$$	$$s_2$$
$$s_2$$	$$s_1$$	$$s_1$$

$$\psi$$	0	1
$$s_1$$	0	0
$$s_2$$	1	1

Пусть на вход автомата подается последовательность знаков (слово) 1,0,0,1,1,0,1 или в более короткой записи 1001101. Проследим, как меняется состояние автомата в процессе обработки этого слова и какая после-довательность знаков формируется на выходе. Для этого рассмотрим таблицу, состоящую из трех строк. В первой строке записаны знаки, поступающие на вход автомата. Во второй строке записываются состояния, в которых оказывается автомат в процессе обработки входного слова. Наконец, в третьей строке записываются знаки, которые появляются на выходе автомата в результате его работы.

(рис 8.2) Табличное задание переходной и выходной функций

вход	1	0	0	1	1	0	1
состояния	$$s_1$$	$$s_2$$	$$s_1$$	$$s_1$$	$$s_2$$	$$s_2$$	$$s_1$$
выход	0	1	0	0	1	1	0

Обработка входной последовательности знаков производится по шагам. На каждом шаге обрабатывается один знак. В таблице каждому шагу обработки соответствует один столбец. Пусть в момент поступления первого знака, которым является 1, автомат находился в состоянии $$s_1$$. Тогда в $$\psi$$ на выходе появится знак 0, а в соответствии с определением функции $$\varphi$$ автомат перейдет в состояние $$s_2$$, которое записывается во вторую строку следующего (второго) столбца таблицы. При поступлении второго знака обрабатываемого слова получим $$\psi (s_2,0)=1$$ (записывается в третью строку второго столбца таблицы) и $$\varphi (s_2,0)=s1$$ (записывается во вторую строку следующего (третьего) столбца таблицы). Процесс обработки следующих знаков происходит аналогичным образом и завершает-ся после обработки последнего знака. В результате исходное слово 1001101 преобразуется в слово 0100110, которое, как можно заметить, является "сдвигом" исходного слова, то есть получается удалением последнего знака из исходного слова и добавлением знака "0" в начало исходного слова.

Помимо рассмотренного табличного способа существует еще графический способ описания (задания) конечных автоматов в виде помеченного ориентированного графа, который называется "диаграмма состояний". Вершины этого графа помечены символами, обозначающими внутренние состояния. Каждое ребро помечено парой символов $$a, b$$, где $$a$$ - входной знак, который вызывает переход в следующее состояние, отвечающее этому ребру, а $$b$$ - выходной знак, который автомат выдает в результате обработки входного знака. Из каждой вершины диаграммы выходит столько дуг, сколько знаков имеется во входном алфавите.

(рис 8.3) Диаграмма состояний сдвигающего автомата

Диаграмма состояний рассмотренного автомата, сдвигающего вправо на один знак входное слово, показана на рис.8.3.

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

Пусть $$\{A,B,S, \varphi, \psi \}$$ - некоторый автомат. Выделим одно состояние, которое назовем начальным и с которого будет начинаться обработка всех входящих слов. Тогда любой входной строке $$\alpha =a(1)a(2)\dots a(k) $$ длины $$k$$, где $$a(i)$$ - знак на $$i$$-м месте входной последовательности, однозначно соответствует строка внутренних состояний, $$\sigma=s(1)s(2)\dots s(k) $$, длины $$k$$, где $$s(i)$$ - состояние после $$i$$-го шага работы, которая получается последовательным применением отображения $$\varphi$$ по формуле (8.1). Аналогично выходная строка $$\beta=b(1)b(2)\dots b(k) $$ длины $$k$$, где $$b(i) $$ - знак на $$i$$-м месте выходной последовательности, однозначно определится последовательным применением отображения $$\varphi$$по формуле (8.2).

Таким образом, автомат можно рассматривать как устройство, преобразующее для заданного начального состояния $$s(0)$$ входную строку $$\аlpha =a(1)a(2) \dots a(k)$$ в строку $$\sigma = s(1)s(2) \dots s(k) $$ и выходную строку $$\beta =b(1)b(2)\dots b(k)$$ и тем самым реализующее функции (преобразования) $$\varphi_k:S \times A^k \to S^k$$ и $$\psi_k:S \times A^k \to B^k$$, которые рекурсивно строятся по функциям $$\varphi$$ и $$\psi$$.

Сеть Петри как модель параллельно выполняемых процессов обработки

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

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

Взаимодействие подсистем приводит к изменению состояния подсистем, всей системы в целом и к выполнению некоторых новых условий, которые могут привести к новым событиям в системе. Для моделирования последовательностей событий, обусловленных логикой работы системы, используется аппарат сетей Петри [37], [38]. В моделях такого типа рассматриваются только события и условия.

Составные части сети. В сетях Петри события и условия представлены абстрактными символами из двух непересекающихся алфавитов, называемых соответственно множеством переходов $$T=\{t_1, t_2, \dots ,t_m\}$$ и множеством мест $$P=\{p_1, p_2, \dots, p_n\}$$. В графическом представлении сетей переходы изображаются "барьерами", а места - кружками (рис.8.4). Условия-места и события-переходы связаны отношением непосредственной зависимости (непосредственной причинно-следственной связи), которое изображается с помощью направленных дуг, ведущих из мест в переходы и из переходов в места. Места, из которых ведут дуги на данный переход, называются его входными местами. Места, на которые ведут дуги из данного перехода, называются его выходными местами.

(рис 8.4) Переход и его входные и выходные места

Во фрагментах сети на рис.8.4 места $$p_1$$ и $$p_2$$ являются входными для перехода $$t_1$$, а места $$p_3$$ и $$p_4$$ - выходными. В этом примере событие-переход $$t_1$$ непосредственно зависит от условий-мест $$p_1$$ и $$p_2$$, а места $$p_3$$ и $$p_4$$ непосредственно зависят от $$t_2$$. В сети некоторые места могут являться входным или выходными одновременно для нескольких переходов.

Разметка сети. Выполнение условия изображается разметкой соответствующего места, а именно помещением некоторого числа фишек (маркеров) в это место. Если число фишек, которые необходимо поместить в некоторое место, достаточно велико, то в это место помещают число, равное требуемому количеству фишек. Число фишек, находящихся в некотором месте $$p$$, называется емкостью соответствующего условия.

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

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

Срабатывание перехода - неделимое действие, изменяющее разметку его входных и выходных мест следующим образом: из каждого входного места изымается по одной фишке, а в каждое выходное место добавляется по одной фишке. Тем самым реализация события, изображаемого переходом, изменяет состояние (емкость) непосредственно связанных с ним условий так, что емкость предусловий, вызвавших реализацию этого события, уменьшается, а емкость постусловий, на которые оно влияет, увеличивается. Переход $$t_1$$ на рис.8.5 а) может сработать, так как оба его входных места $$p_1$$ и $$p_2$$ содержат фишки, а после срабатывания $$t_1$$ разметка его входных и выходных мест изменяется так, как показано на рис.8.5 б).

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

Если несколько переходов могут сработать и имеют общее входное место (как переходы $$t_1$$ и $$t_2$$ на рис.8.5 а)), то срабатывает только один, любой из них. При этом может оказаться, что, сработав, этот переход лишит возможности сработать другие переходы (рис.8.5, б) и г)). Таким способом в сети моделируется конфликт между событиями, когда реализация одного события может исключить возможность реализации других. В сети никак не указывается, каким образом конфликт следует фактически разрешить. Считается, что решение о том, какое из конфликтующих событий следует реализовать, принимается вне формализма сети, т.е. поведение сети носит недоопределенный недетерминированный характер. Аналогичный конфликт возникает в том случае, когда несколько переходов могут сработать и они имеют общие выходные места, как переходы $$t_3$$ и $$t_4$$ (рис.8.5, б и в).

(рис 8.5) Пример функционирования сети

В процессе функционирования сети происходит смена разметок мест как результат срабатывания ее переходов. Сеть останавливается, если ни один из ее переходов не может сработать как, например, на рис.8.5, в) и г).

Формальное определение сети Петри

Чтобы можно было использовать сети Петри для анализа процессов обработки, необходимо иметь точное определение.

Графом сети Петри будем называть тройку ($$Р, Т, F$$), где

$$P$$ - непустое множество элементов сети, называемых местами,

$$T$$ - непустое множество элементов сети, называемых переходами,

$$F\subseteq Р \times Т \bigcup T \times P$$- отношение инцидентности,

и для ($$Р, Т, F$$) выполнены следующие условия:

$$P \bigcap T=\varnothing$$ (множества мест и переходов не пересекаются);

$$ (F \ne \varnothing) \wedge (\forall x \in P \bigcup T, \exists y \in P \bigcup T : xFy \vee yFx))$$ (т.е. любой элемент сети инцидентен хотя бы одному элементу другого типа);

если для произвольного элемента сети $$x \in X$$ обозначить через $$*x$$ множество его входных элементов $$\{y|yFx\}$$, а через $$x*$$ - множество его выходных элементов $$\{y|xFy\}$$, то

$$\forall p_1,p_2 \in P:(^{\cdot}p_1=^{\cdot}p_2)\wedge(p_1^{\cdot}=p_2^{\cdot})\Rightarrow (p_1=p_2), $$

то есть сеть не содержит пары мест, которые инцидентны одному и тому же множеству переходов.

Графическим представлением сети служит двудольный ориентированный граф с двумя типами вершин; вершины-места изображаются кружочками, вершины-переходы - барьерами. Из вершины $$х$$ в вершину $$y$$ ведет дуга, если и только если $$xFy$$.

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

Сеть Петри - это набор $$N=\{Р, Т, F, Ф, M_0\}$$, где $$(Р, Т, F) $$ - конечная сеть (множество $$X= Р \bigcup T$$ конечно), a $$Ф:P \times T \bigcup T \times P \to N$$ и $$M_0 :P\to N$$- две функции, называемые соответственно кратностью дуг и начальной разметкой. Первая сопоставляет каждой дуге число $$n \ge 0$$ (кратность дуги). Если $$n>0$$, то в графическом представлении сети число $$n$$ выписывается рядом с короткой чертой, пересекающей дугу. Часто такая дуга будет также заменяться пучком из $$п$$ дуг, соединяющих соответствующие элементы сети. Условимся никак не отмечать кратность дуг, равную 1. Такую сеть будем называть ординарной. Вторая функция сопоставляет каждому месту $$p \in Р$$ некоторое число $$M_0(p) \in N$$ (разметка места). В графическом представлении сети разметка места $$р$$ изображается помещением в вершину-кружок числа $$M_o(р)$$ или, если это число невелико, соответствующего числа точек (фишек).

Разметка сети $$N$$ - это функция $$M:P \to N$$. Если предположить, что все места сети $$N$$ строго упорядочены каким-либо образом, т.е. $$P=(p_1, p_2, \dots , p_n)$$, то разметку $$М$$ сети (в том числе начальную разметку) можно задать как вектор целых неотрицательных чисел

$$M=\begin{pmatrix}m_1\\m_2\\\vdots\\m_n\end{pmatrix}$$

такой, что для любого $$i, 1 <i<n, m_i = M(p_i) $$.

На основе отношения инцидентности $$F$$ можно ввести функцию инцидентности $$Ф: P \times T\bigcup T \times P \to N$$, которая определяется выражением

$$Ф(х,у)=\begin{cases}n \in N^+, \mbox {\ если\ } xFy\\o, \mbox {\ если\ } \neg xFy\end{cases}$$

Значения функции $$Ф(x, y) $$ можно трактовать как кратность дуги между вершинами сети $$x$$ и $$y$$. Если $$Ф(x, y) = 0$$, то это означает, что между вершинами $$x$$ и $$y$$ дуги нет.

Если места сети упорядочены, то можно каждому переходу $$t$$ сопоставить два целочисленных вектора $$ 'F(t) $$ и $$F'(t) $$ длиной $$n$$, где $$n = |Р|$$:

$$Ф(t)=\begin{pmatrix}b_1\\b_2\\\vdots\\b_n\end{pmatrix}, \; где\; b_i=Ф(p_i,t) $$

и

$$Ф(t)=\begin{pmatrix}b_1\\b_2\\\vdots\\b_n\end{pmatrix}, \; b_1=Ф(t,p_i)$$

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

Переход $$t$$ может сработать при некоторой разметке $$М$$ сети $$N$$, если $$\forall p \in 't M(p) \ge Ф(p,t) $$, то есть каждое входное место $$p$$ перехода $$t$$ имеет разметку, не меньшую, чем кратность дуги, соединяющей $$р$$ и $$t$$. Это условие можно переписать в векторной форме следующим образом: $$M \ge 'Ф(t) $$.

Предполагается, что для векторов $$x \in R^n, y\in R^n$$ выражение $$x \ge y$$ озна-чает, что $$x_i \ge y_i, i= 1, 2,\dots, n$$.

Из определения векторов $$'Ф(t) $$ и $$Ф'(t) $$ ясно, что вектор $$ 'Ф(t) $$ является столбцом матрицы $$D^-$$, а вектор $$Ф'(t) $$ является столбцом матрицы $$D^+$$

$$D^-=\begin{pmatrix} Ф(p_1,t_1)Ф(p_1,t_2)\dotsФ(p_1,t_m)\\ Ф(p_2,t_1)Ф(p_2,t_2)\dotsФ(p_2,t_2)\\ \vdots\vdots\ddots\vdots\\ Ф(p_n,t_1)Ф(p_n,t_2)\dots Ф(p_n,t_m) \end{pmatrix}, D^+=\begin{pmatrix} Ф(t_1,p_1)Ф(t_2,p_1)\dotsФ(t_m,p_1)\\ Ф(t_1p_2)Ф(t_2,p_2)\dotsФ(t_m,p_2)\\ \vdots\vdots\ddots\vdots\\ Ф(t_1,p_n)Ф(t_2,p_n)\dots Ф(t_m,p_n) \end{pmatrix}$$

Векторы $$'Ф(t) $$ и $$Ф'(t) $$ могут быть представлены как произведения $$D^- \times \tau_i $$ и $$D^+ \times \tau_i $$ матриц $$D^- $$ и $$D^+ $$ на вектор $$х_i $$ вида

$$\tau_i=\begin{pmatrix}0\\0\\\vdots\\1\\\vdots\\0\end{pmatrix}\mbox{i-я строка}$$

у которого все компоненты равны 0, кроме $$i $$-й компоненты, равной 1.

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

Срабатывание перехода $$t_i $$ при разметке $$M $$ порождает разметку $$М' $$ по следующему правилу:

$$\forall p \in P\; М(р) = М(р)-Ф(р,t_i) + Ф(t_i,р) $$

В матричном виде изменение разметки при срабатывании перехода $$t_i $$ описывается выражением

$$М' = М-'Ф(t_i)+Ф'(t_i) \mbox{или} M'=M-D^- *\tau_i+D^+*\tau_i $$

Обозначив $$D=D^+ - D^- $$, получим еще более краткую запись для выражения (8.4)

$$M=M+D^-*\tau_t $$

Таким образом, срабатывание перехода $$t$$ изменяет разметку так, что разметка каждого его входного места $$p$$ уменьшается на $$Ф(p,t)$$, т.е. на кратность дуги, соединяющей $$р$$ и $$t$$, а разметка каждого его выходного места увеличивается на $$Ф(t,р) $$, т.е. на кратность дуги, соединяющей $$t$$ и $$р$$.

Элемент матрицы $$D=D^+-D-$$, находящийся в $$i$$-й строке и $$j$$-м столбце, представляет собой разность числа появившихся и удаленных в $$i$$-м месте фишек в результате срабатывания $$j$$-го перехода.

На множестве разметок можно ввести отношение непосредственного следования разметок:

$$М \triangleright М \leftrightarrow \exists t \in Т:(М\ge Ф(t) \wedge(М'= - 'Ф(t) + Ф'(t)) $$

Будем использовать уточняющее обозначение $$ М^t \triangleright М'$$, если $$ М'$$ непосредственно следует после $$М$$ в результате срабатывания перехода $$ t$$. Говорят, что разметка $$М'$$ достижима от разметки $$ М$$, если существует последовательность разметок $$ М, М_1, М_2, \dots , М'$$ и слово $$\tau= t_{1t2} \dots t_k$$ в алфавите $$ Т$$, такие что

$$ М^{t_1}\triangleright М^{t_2} \triangleright М^{t_2} \dots \triangleright М'$$

Слово $$\tau$$ в этом случае называется последовательностью срабатываний, ведущих от $$М$$ к $$М'$$. Обобщим отношения непосредственного следования до отношения "$$ М'$$ достижима от $$ М$$", используя обозначение $$М \triangleright М$$ или $$M^{\tau} \triangleright М'$$ , если уточняется последовательность срабатываний (последовательность может быть пустой, т.е. $$М'$$ не достижима от $$М$$).

Множество $$\{М'| М\triangleright М'\}$$ разметок, достижимых в сети $$N$$ от разметки $$М$$, обозначим через $$R(N, М)$$. Множество $$R(N) = R(N, M_0)$$ , т.е. множество всех разметок, достижимых в $$N$$ от начальной разметки $$М_0$$, называют множеством достижимых разметок сети $$N$$ (заметим, что $$M \in R(N, М)$$ и $$M_0 \in R(N)$$).

Множеством последовательностей срабатываний сети $$N$$, или свободным языком сети $$N$$, называется множество

$$L(N) =\{\tau \in T'| \exists M\in R(N):M_0^{\tau}\triangleright M\)$$

то есть множество всех последовательностей срабатываний, ведущих от $$М_0$$ к каждой достижимой в $$N$$ разметке.

На рис.8.6 изображена сеть Петри, на примере которой поясним данные выше определения. В этой сети $$Р=\{p_1, p_2, p_3\}, T=\{t_1, t_2, t_3\}$$. Функция инцидентности $$Ф$$ задается с помощью следующих двух таблиц, в которых на пересечении строки $$х$$ и столбца $$y$$ стоит число $$Ф(x, y)$$:

	$$p_1$$	$$p_2$$	$$p_3$$
$$t_1$$	1	1	0
$$t_2$$	0	0	1
$$t_3$$	0	2	0
$$t_4$$	1	0	0

	$$t_1$$	$$t_2$$	$$t_3$$	$$t_4$$
$$p_1$$	1	1	0	0
$$p_2$$	0	2	0	0
$$p_3$$	0	0	1	1

Начальная разметка $$M_0$$ задается следующим образом: $$M_0(p_1) = 1, M_0(p_2) = 2, M_0(p_3) =0$$, или в векторной форме: $$M_0 = (1, 2, 0)^т$$.

При разметке $$M_0$$ могут сработать переходы $$t_1$$ и $$t_2$$, так как $$M_0 = (1,2,0)^т > 'Ф(t_1) = (1,0,0)^т, M_0 > 'Ф(t_2) = (1,2,0)^т$$. Переходы $$t_3$$ и $$t_4$$ не могут сработать, так как вектор начальной разметки $$M_o$$ не покрывает векторы $$ 'Ф(t_3) = (0, 0, 1)^т$$, и $$ 'Ф(t_4 ) = (0, 0, 1)^т$$.

(рис 8.6) Пример сети Петри

В результате срабатывания перехода $$t_1$$ разметка $$M_0$$ сменяется на разметку (1, 3, 0), а в результате срабатывания перехода $$t_2$$ разметка $$М_0$$ сменяется на разметку (0, 0, 1) . Обе новые разметки непосредственно следуют после $$M_0$$ в рассматриваемой сети. Можно представить возможные изменения разметок сети $$N$$, происходящие в результате срабатывания ее переходов, в виде графа разметок - ориентированного графа, множество вершин которого образовано множеством $$R(N)$$ достижимых в $$N$$ разметок. Из вершины $$М$$ в вершину $$М'$$ ведетa дуга, помеченная символом перехода $$t$$, если и только если $$М^t \triangleright М'$$ . На рис.8.7 показан начальный фрагмент графа разметок сети на рис.8.6. Этот граф бесконечен, так как множество $$R(N)$$ достижимых разметок бесконечно для рассматриваемой сети.

Разметка $$M \in R(N)$$ называется тупиковой, если в сети $$N$$ не существует ни одного перехода, который может сработать при этой разметке. Для рассматриваемой сети тупиковыми являются разметки (0, 2, 0), (0, 3, 0), (0,4,0),..., (0, n, 0)...

Легко видеть, что если выделить путь по дугам графа разметок, начинающийся в вершине $$М$$ и заканчивающийся в вершине $$М'$$, и выписать подряд все встречающиеся символы переходов, то полученное слово образует последовательность срабатываний, ведущих от $$М$$ к $$М'$$. Множество всех слов, которые получены выписыванием символов переходов вдоль путей, начинающихся в $$M_0$$, образует множество последовательностей срабатываний сети, или ее свободный язык. Так, язык рассматриваемой сети включает слова $$\{\epsilon , t_1, t_2, t_1t_1, t_1t_2, t_2t_3, t_2t_4, t_1t_1t_1, t_1t_1t_2t, t_1t_2t_3, t_1t_2t_4, t_2t_4t_1, t_1t_1t_1t_1, t_1t_1t_1t_2, \dots \}$$.

Основные задачи анализа процессов обработки, решаемые с использованием сетей Петри

В процессе функционирования сети Петри некоторые ее места могут накапливать неограниченное число фишек. Примером такого места может служить место $$р_2$$ в сети на рис.8.6. Если интерпретировать места как

(рис 8.7) Граф разметок сети Петри

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

Определение. Место $$р$$ в сети Петри $$N=(Р, Т, F, Ф, М_0)$$ называется ограниченным, если существует число $$n$$, такое что для любой достижимой в сети разметки $$М$$ справедливо неравенство $$М(р)< n$$. Сеть $$N$$ называется ограниченной сетью, если любое ее место ограничено.

Ясно, что множество достижимых разметок $$R(N)$$ конечно, если и только если $$N$$ - ограниченная сеть. В сети на рис.8.6 места $$р_1$$, и $$р_3$$ ограничены, так как каждое из них может содержать не более одной фишки. В то же время место $$р_2$$ не ограничено, и поэтому эта сеть не является ограниченной.

Определение. Место $$р$$ называется безопасным, если для всякой достижимой разметки $$M \in R(N)$$ выполняется неравенство $$М(р)<1$$; соответственно, сеть безопасна, если все ее места безопасны.

Любая достижимая в безопасной сети разметка представляет собой вектор из 0 и 1. Сеть, показанная на рис.8.6, не является безопасной.

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

Определение. Сеть, в которой сумма фишек во всех ее местах остается постоянной в процессе работы сети, то есть

$$\sum_{p \in P}M_1(p)=\sum_{p \in P}M_2(p),\\ \forall M_1, M_2 \in R(N)$$

называется сохраняющей (консервативной).

Условие сохранения числа фишек в сети - это очень сильное ограничение. Например, из него немедленно следует, что число входов в каждый переход должно равняться числу выходов (с учетом кратности). Если бы это было не так, запуск перехода изменил бы число фишек в сети.

Часто фишки в сети Петри моделируют различные ресурсы. Однако взаимно однозначного соответствия между фишками и ресурсами нет. Фишка может представлять как один ресурс, так и несколько ресурсов сразу. Во втором случае фишка может использоваться для создания кратных фишек (по одной на ресурс) путем запуска перехода с большим числом выходов, чем входов. Поэтому определение свойства сохраняемости сети целесообразно сделать более общим, заменив простую сумму фишек на сумму с весами. Фишкам, не являющимся важными, можно присвоить нулевой вес; другим фишкам можно присвоить весы 1, 2, 3 или любое другое положительное число.

Определение. Сеть Петри называется сохраняющей (консервативной) по отношению к вектору весов $$\аlpha=(\alpha_1, \alpha_2, \dots, \alpha_n)$$, где $$n$$ - число мест в сети, если

$$\sum_{i=1}^n \alpha_i*M_1(p_1)=\sum_{i=1}^n \alpha_1*M_2(p_1) \; \forall M_1, M_2 \in R(N)$$

Сохраняющая сеть Петри является сохраняющей по отношению к вектору весов $$(1, 1, \dots , 1)$$. Следует исключить из рассмотрения нулевой вектор весов, поскольку все сети являются сохраняющими по отношению к нулевому вектору весов.

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

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

Уровень 0: переход $$t$$ обладает активностью уровня 0 и называется мертвым, если он никогда не может быть запущен.

Уровень 1: переход $$t$$ обладает активностью уровня 1 и называется потенциально живым, если существует такая разметка $$M' \in R(N,M_0)$$, что $$t$$ разрешен в $$M'$$. Уровень 2: переход $$t$$ обладает активностью уровня 2, если для всякого целого $$n$$ существует последовательность запусков, в которой $$t$$ присутствует по крайней мере $$n$$ раз.

Уровень 3: переход $$t$$ обладает активностью уровня 3, если существует бесконечная последовательность запусков, в которой $$t$$ присутствует неограниченно часто.

Уровень 4: переход $$t$$ обладает активностью уровня 4 и называется живым, если для всякой $$M' \in R(N,M_0)$$ переход $$t$$ является потенциально живым для сети Петри $$N$$ с начальной маркировкой $$M'$$.

Сеть Петри называется живой, если все ее переходы являются живыми.

В качестве примера, иллюстрирующего уровни активности, рассмотрим сеть Петри на рис.8.8. Переход $$t_0$$ не может быть запущен никогда; он мертвый. Переход $$t_1$$ можно запустить только один раз; он обладает активностью уровня 1. Переход $$t_2$$ может быть запущен произвольное число раз, но это число зависит от числа запусков перехода $$t_3$$. Если мы хотим запустить $$t_2$$ пять раз, мы запускаем пять раз $$t_3$$, затем $$t_1$$ и после этого пять раз $$t_2$$. Однако, как только запустится $$t_1$$ ($$t_1$$ должен быть запущен до того, как будет запущен $$t_2$$), число возможных запусков $$t_2$$ станет фиксированным. Следовательно, $$t_2$$ обладает активностью уровня 2, но не уровня 3. С другой стороны, переход $$t_3$$ можно запускать бесконечное число раз, и поэтому он обладает активностью уровня 3, но не уровня 4, поскольку, как только запустится $$t_1$$, переход $$t_3$$ больше запустить будет нельзя.

(рис 8.8) Сеть Петри, иллюстрирующая различные уровни активности переходов

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

Формально задача о достижимости состоит в следующем: для сети Петри $$N$$ с начальной разметкой $$M_0$$ и заданной разметки $$M$$ установить справедливость включения $$M \in R(N,M_0)$$. Иными словами, требуется выяснить, существует ли допустимая последовательность срабатываний переходов $$\tau =t_{i_1}, t_{i_2} \dots t_{i_k}$$, переводящая сеть Петри из начальной разметки $$M_0$$ в заданную разметку $$M$$, то есть $$М_0^{\tau} \triangleright М$$.

Близкой по смыслу к задаче о достижимости является задача о покрываемости. Она заключается в том, чтобы для данной сети Петри $$N$$ с начальной маркировкой $$M_0$$ и заданной маркировки $$M$$ определить, существует ли такая достижимая маркировка $$M' \in R(N,M_0)$$, что $$M' \ge M$$.

Напомним, что отношение $$M' \ge M$$ истинно, если каждый элемент маркировки $$M'$$ не меньше соответствующего элемента маркировки $$M$$.

Матричный метод анализа сетей Петри

Матричный метод основан на выражении (8.5), связывающим разметки сети, которые были до и после срабатывания некоторого перехода и матрице $$D$$, описывающей работу сети.

Пусть начальная разметка сети равна $$M_0$$. Если в сети допустима последовательность срабатывания переходов $$t_{i_1}, t_{i_2}, \dots, t_{i_k}$$, то выполняются следующие соотношения

$$M_1 =M_0+D*t_k\\ M_1=M_l + D*t_{i_2}=M_0 + D*t_{i_1}+D*t_{i_2}\\ M_3=M_2+D*t_{i_3}=M_1+D*t_{i_2}+D*t_{i_3}=M_0+D*t_{i_1}+D*t_{i_2}+D*t_{i_3}\\ \dots \dots \dots \dots\\ M_k=M_0+D*t_{i_1}+D*t_{i_2}+\dots+D*t_{i_k}=M_0+D(t_{i_1}+t_{i_2}+\dots +t_{}i_k)$$

Обозначив $$\tau=t_{i_1}+t_{i_2}+\dots+t_{i_k}$$,получим

$$M_k=M_0+D* \tau\\ M_k-M_0=D* \tau$$

Из-за того, что вектор тявляется суммой векторов вида (8.2) он должен быть целочисленным неотрицательным вектором. Выполнение соотношения (8.6) для некоторого целочисленного неотрицательного вектора $$\tau$$ является необходимым условием достижимости разметки $$М_к$$ из началь-ной разметки $$М_0$$.

Выражение (8.7) является системой линейных неоднородных уравнений относительно неизвестных компонент вектора $$\tau$$. Следует заметить, что целочисленное неотрицательное решение уравнения (8.7), как правило, не определяет однозначно порядок срабатывания переходов, потому что от порядка суммирования векторов $$t_{i_k}$$ вида (8.2) сумма $$\tau=t_{i_1}+t_{i_2}+\dots+t_{i_k}$$ не зависит. Для нахождения требуемого порядка срабатывания переходов необходимо проводить дополнительные исследования.

(рис 8.9) Сеть Петри

Рассмотрим пример решения матричным методом задачи о достижимости. Спрашивается, достижима ли разметка $$M_k=(1\; 1\; 2\; 2)^T$$ для сети Петри, изображенной на рис.8.9?

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

Матрица $$D$$ для данной сети Петри имеет вид

$$D=\begin{pmatrix}000\\ 10-1\\ 010\\ 001\end{pmatrix}$$

Матричное уравнение (8.6) для определения последовательности срабатываний переходов имеет вид $$\begim{pmatrix}000\\10-1\\010\\001\end{pmatrix}*\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}=\begin{pmatrix}1\\2\\2\end{pmatrix}$$

Без первого уравнения, которое тривиально выполняется, имеем систему трех уравнений с тремя неизвестными $$\begim{pmatrix}10-1\\010\\001\end{pmatrix}*\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}=\begin{pmatrix}0\\1\\2\\2\end{pmatrix}$$

Из второго и третьего уравнений получаем $$x_2=2, x_3=2$$, а из первого $$-x_1=3$$. Таким образом, в качестве решения имеем целочисленный неотрицательный вектор

$$x=\begin{pmatrix}3\\2\\2\end{pmatrix}$$

Этот вектор не определяет порядок срабатывания переходов. Среди последовательностей срабатывания есть невыполнимые, например, $$t_1t_1t_1t_3t_3t_2t_2$$. Среди последовательностей срабатывания переходов, удовлетворяющих вектору, необходимо искать допустимые. Допустимых после-довательностей может быть много, а может и не быть вовсе. Для данного примера допустимой последовательностью является последовательность $$t_1t_2t_1t_2t_1t_3t_3$$ или последовательность $$t_1t_2t_3t_2t_1t_3t_1$$.

Наличие неотрицательного положительного решения у линейного уравнения для определения последовательности срабатывания является только необходимым условием и не гарантирует реального существова-ния такой последовательности. Например, решая задачу о достижимости разметки $$M_k=(1\;1\;0\;2)^T$$ для описанной выше сети Петри, в качестве решения мы получим неотрицательный целочисленный вектор

$$X=\begin{pmatrix}3\\2\\2\end{pmatrix}$$

Однако реальной последовательности, приводящей к требуемой разметке, не существует, так как для срабатывания перехода $$t_3$$ необходимо наличие в месте $$p_3$$ маркера. Но фишка, попавшая в $$p_3$$, не может покинуть эту позицию.

Пример 2 (решение матричным методом задачи о достижимости).

Рассмотрим сеть

(рис )

и исследуем достижимость разметки $$\begin{pmatrix}1\\7\\0\\1\end{pmatrix}$$ из начальной разметки $$\begin{pmatrix}1\\0\\1\\0\end{pmatrix}$$

Матрица $$D$$ имеет вид

$$D=\begin{pmatrix}000\\-110\\-11-1\\0-11\end{pmatrix}$$

Матричное уравнение для определения последовательности срабатываний переходов имеет вид

$$\begim{pmatrix}000\\-110\\-111\\0-11 \end{pmatrix}*\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}=\begin{pmatrix}0\\7\\-1\\1\end{pmatrix}$$

Без первого уравнения, которое тривиально выполняется, имеем систему

$$\begim{pmatrix}-110\\-11-1\\0-11 \end{pmatrix}*\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}=\begin{pmatrix}7\\-1\\1\end{pmatrix}$$

Складывая второе и третье уравнения, получим $$x_1=0$$. Из первого уравнения получаем $$x_2=7$$, а из третьего -$$x_3=8$$. Таким образом, в качестве решения имеем целочисленный неотрицательный вектор

$$x=\begin{pmatrix}0\\7\\8\end{pmatrix}$$

Этот вектор не определяет порядок срабатывания переходов. Среди последовательностей срабатывания есть невыполнимые, например

$$\overbrace{t_2t_2\dots t_2}^{7раз}\overbrace{t_{3t3} \dots t_3}^{8 раз}$$

Среди последовательностей срабатывания переходов, удовлетворяющих вектору, необходимо искать допустимые. Допустимых последовательностей может быть много, а может и не быть вовсе. Для данного примера допустимой последовательностью является последовательность $$t_3t_2t_3t_2t_3t_2t_3t_2t_3t_2t_3t_2t_3t_2t_3$$.

Матричный подход может быть использован для вектора весов, относительно которого сеть Петри является сохраняющей (консервативной). Пусть $$\аlpha=(\alpha_1, \alpha_2, \dots , \alpha_n)$$ - вектор-строка искомых весов. В соответствии с приведенным выше определением консервативность сети заключается в выполнении равенства (8.6). Обе части этого равенства можно рассматривать как скалярные произведения вектора $$\alpha$$ на векторы любых двух достижимых разметок. Если в качестве одной из разметок взять начальную разметку $$M_0$$, а в качестве второй - любую достижимую разметку, то из (8.6) следует, что $$\alpha*M-\alpha -M_0=\alpha (M-M_0)=0$$. Из формулы (8.5) следует, что $$M-M_0=D*\tau$$. В результате получаем, что $$\alpha*D*\tau=0$$ для всех векторов $$\tau$$, соответствующих достижимым разметкам. Равенство выполняется, если $$\alpha*D=0$$. Это матричное выражение представляет собой линейное однородное уравнение относительно весов, составляющих вектор $$\аlpha$$.

Для сети, изображенной на рис.8.10, найдем матричным методом вектор весов $$\alpha$$, относительно которого она является сохраняющей. Эта сеть моделирует два взаимодействующих процесса обработки, использующих общий ресурс (описывается местом $$p_5$$).

(рис 8.10) Модель двух процессов, использующих неделимый ресурс

Матрица $$D$$ для данной сети имеет вид

$$D=\begin{pmatrix}-1010\\0-101\\10-10\\010-1\\-1-111\end{pmatrix}$$

Легко заметить, что эта матрица имеет ранг 2 (третий столбец равен первому, умноженному на -1, а четвертый столбец равен второму, умноженному на -1). Поэтому система уравнений $$\alpha*D=0$$ для вектора весов $$\alpha=(\alpha_1, \alpha_2, \alpha_3 \alpha_4, \alpha_5)$$ включает в себя только два уравнения

$$\begin{cases}-\alpha_1+\alpha_3-\alpha_5=0\\\alpha_2+\alpha_4-\alpha_5=0\end{cases}$$

Существует бесконечно много решений этой системы, которые могут быть получены из выражений

$$\begin{cases}\alpha_1=\alpha_3-\alpha_5\\\alpha_2=\alpha_4-\alpha_5\end{cases}$$

при произвольном задании весов $$\alpha_3, \alpha_4, \alpha_5$$. Из этих выражений видно, что сеть не является строго сохраняющей, т. к. вектор (1, 1, 1, 1, 1) не является решением системы. В качестве вектора весов, относительно которого сеть является сохраняющей, нас интересуют только неотрицательные решения. Задавая $$\alpha_5 = 0, \alpha_3 =1, \alpha_4=1$$, , получим $$\alpha_1=1, \alpha_2=1$$. Вектор весов (1, 1, 1, 1, 0), являющийся решением системы, означает, что сеть сохраняет суммарное количество фишек во всех местах, за исключением места $$p_5$$ (количество фишек в месте $$p_5$$ не учитывается при подсчете обще-го числа в сети). Еще одно решение (1, 1, 2, 2, 1) соответствует случаю, когда фишки в местах $$p_3$$ и $$p_4$$ учитываются при подсчете взвешенной суммы фишек в сети с коэффициентом 2.