Las reds de petri

Introdução às Redes de Petri

Prof. Dr. Carlos Renato Lisboa Francês Laboratório de Computação Aplicada – LACA Universidade Federal do Pará - UFPA rfrances@ufpa.br Agosto de 2003

1. Redes de Petri
Rede de Petri é uma técnica de modelagem que permite a representação de sistemas, utilizando como alicerce uma forte base matemática [MAC96]. Essa técnica possui a particularidade de permitirmodelar sistemas paralelos, concorrentes, assíncronos e não-determiníticos [VAL80]. A representação gráfica de uma rede de Petri básica é formada por dois componentes: um ativo chamado de transição (barra) e outro passivo denominado lugar (círculo). Os lugares equivalem às variáveis de estado e as transições correspondem às ações realizadas pelo sistema [MAC96]. Esses dois componentes são ligadosentre si através de arcos dirigidos. Os arcos podem ser únicos ou múltiplos. A figura 1 mostra os elementos básicos de um grafo associado às redes de Petri.

Lugar P 0 Arco

Lugar P 1

T ransição t 0

Figura 1. Grafo e seus Elementos Básicos. 1.1. Definições As redes de Petri podem ser enfocadas através de três fundamentações diferentes. A primeira utiliza a teoria bag como suporte. A segundausa os conceitos da álgebra matricial. A última se fundamenta na estrutura definida por relações. A seguir são apresentadas as definições formais de cada uma dessas fundamentações. • Fundamentações para Redes de Petri Definição 1: uma rede de Petri R é uma quíntupla R = (P, T, I, O, K), onde P = {p1, p2,...,pn} é um conjunto finito não-vazio de lugares, T = {t1, t2,..., tm} é um conjunto finitonão-vazio de transições. I : T → P é um conjunto de bags 1 que representa o mapeamento de transições para lugares de entrada. O : T → P é um conjunto de bags que representa o mapeamento de transições para lugares de saída. K : P → N é o conjunto da capacidades associadas a cada lugar, podendo assumir um valor infinito [PET81].

1

Bag é uma generalização do conceito de conjunto que admite arepetição de elementos. Na notação de bags, utiliza-se [ ], enquanto que para denotar conjuntos, utiliza-se { } [MAC96].

Para exemplificar a definição 1, supõe-se que se deseje representar um ano letivo de uma Universidade. O ano letivo começa com o primeiro período (semestre) letivo, seguido das primeiras férias (de julho), logo após, tem-se o segundo período letivo, e finalmente as férias definal de ano. Assim, o ano letivo poderia ser representado conforme a figura 2.
Retornar 1oPeríodo 1 Período
o

Férias2

GozarFérias2 GozarFérias1

Férias1 Retornar 2oPeríodo

2oPeríodo

Figura 2. Ano Letivo Representado Graficamente em Redes de Petri. A figura 2 pode ser descrita da seguinte forma, utilizando-se a definição 1: RAno_Letivo = ( P, T, I, O, K ), onde o conjunto de lugares Pé P = {1oPeríodo, Férias1, 2oPeríodo, Férias2}; o conjunto de transições T é T = {GozarFérias1, Retornar2oPeríodo, GozarFérias2, Retornar1oPeríodo}; o conjunto de bags de entrada I é I = { I (GozarFérias1) = [1oPeríodo], I (Retornar2oPeríodo) = [Férias1], I (GozarFérias2) = [2oPeríodo], I (Retornar1oPeríodo) = [Férias2] }; o conjunto de bags de saída O é O = {O (GozarFérias1) = [Férias1], O(Retornar2oPeríodo) = [2oPeríodo], O (GozarFérias2) = [Férias2], O (Retornar1oPeríodo) = [1oPeríodo] };

e o conjunto de capacidades dos lugares é K = { K1oPeríodo = 1, K Férias1 = 1, K2oPeríodo = 1, K Férias2 = 1}. Definição 2: a estrutura de uma rede de Petri, segundo o ponto de vista matricial, é uma quíntupla R = (P, T, I, O, K), onde P é um conjunto finito de lugares. T é um conjunto finito detransições, I : P x T → N é a matriz de pré-condições. O : P x T → N é a matriz de pós-condições. K é o vetor das capacidades associados aos lugares (K : P → N) [PET81]. Tomando-se como base novamente a figura 2, tem-se: Os conjuntos de lugares e transições são idênticos àqueles vistos para a definição1. A matriz I (pré-condições) é
GozarFérias1 1 0 0 0 Retornar2oPeríodo 0 1 0 0 GozarFérias2 0...