Solução de Alguns Exercícios
Tópicos Avançados em
Engenharia de Computação
Redes de Petri Aplicadas à
Síntese de Sistemas Digitais
Norian Marranghello – Setembro/Dezembro de 2003
n
n
Seja P um vetor coluna nx1;
Seja M0 a marcação inicial; e
Seja Mi uma marcação alcançável.
n
n
n
Devemos mostrar que: M0 • P = Mi • P, ∀ Mi.
n
Mi ∈ [ M0 〉 , ∃ σ / M0 [ σ 〉 Mi
n
Então: Mi = δ (M0 , σ) = M0 + ƒ(σ) • D
Solução de Alguns Exercícios
l2
n
Substituindo Mi: M0 • P = ( M0 + ƒ(σ) • D ) • P
M0 • P = M0 • P + ƒ(σ) • D • P
De onde: ƒ(σ) • D • P = 0
Como precisamos ter ƒ(σ) ≠ 0
A RdP será conservativa sse
∃P≠0
D•P=0
Norian Marranghello – 2003 – Redes de Petri Aplicadas à Síntese de Sistemas Digitais
t2
n
n
l4
n
l3
Como: M0 • P = Mi • P e Mi = M0 + ƒ(σ) • D
Solução de Alguns Exercícios
Utilizando a equação fundamental das RdP,
analise a alcançabilidade da rede abaixo.
t1
n
n
Norian Marranghello – 2003 – Redes de Petri Aplicadas à Síntese de Sistemas Digitais
l1
Para mostrar a condição de conservação é
necessário mostrar um vetor de pesos, não nulo,
para o qual a soma ponderada sobre todas as
marcações alcançáveis é constante.
Solução de Alguns Exercícios
n
n
n
Determine a condição de conservação das RdP
utilizando a equação fundamental das RdP.
Norian Marranghello – 2003 – Redes de Petri Aplicadas à Síntese de Sistemas Digitais
Solução de Alguns Exercícios
n
n
t3
Norian Marranghello – 2003 – Redes de Petri Aplicadas à Síntese de Sistemas Digitais
Mi ∈ [ M0 〉 à ∃ σ / M0 [ σ 〉 Mi
Isto significa que ƒ(σ) é solução para
Mi = M 0 + χ • D
(Eq.1)
χ em:
Então se Mi é alcançável a Eq.1 tem solução não
negativa e se esta equação não tem solução Mi não
é alcançável a partir de M0.
Norian Marranghello – 2003 – Redes de Petri Aplicadas à Síntese de Sistemas Digitais
1
Solução de Alguns Exercícios
n
Para a rede proposta no enunciado:
D- =
1 1 1 0
0 0 0 1
0 0 1 0
0 -1 -1 0
D = 0 +2 +1 -1
0 0 -1 +1
D+ =
1 0 0 0
0 2 1 0
0 0 0 1
Solução de Alguns Exercícios
Alguns problemas podem ser identificados com a
equação fundamental das RdP, por exemplo:
ü A matriz D não reflete adequadamente a estrutura da
RdP, uma vez que as entradas de D+ e D-, referentes a
laços, se cancelam ao serem transportadas para D; e
ü O vetor de disparos não possui informação sobre a
seqüência na qual as transições são disparadas.
n
n
Assim temos: M1 = M0 + e(t3) • D = (1,0,0,1)
n
M0 [ƒ(σ = t3 t2 t3 t2 t1) = (1,2,2)〉 Mσ = (1,3,0,0)
n
My = (1,7,0,1) ∉ [M0〉 , ¬ ∃ σ / χ = ƒ(σ)
Sendo a marcação
inicial M0=(1,0,1,0),
temos t3 habilitada.
Norian Marranghello – 2003 – Redes de Petri Aplicadas à Síntese de Sistemas Digitais
n
Solução de Alguns Exercícios
Norian Marranghello – 2003 – Redes de Petri Aplicadas à Síntese de Sistemas Digitais
Solução de Alguns Exercícios
n
Determinar se a marcação Mx = (0,0,0,1) é
alcançável a partir da marcação inicial M0 =
(1,0,0,0) na RdP:
l2
l1
Portanto, embora a solução para a equação
fundamental seja uma condição necessária para a
determinação da alcançabilidade em RdP, ela não
é suficiente.
t2
t1
l4
l3
Norian Marranghello – 2003 – Redes de Petri Aplicadas à Síntese de Sistemas Digitais
Solução de Alguns Exercícios
Norian Marranghello – 2003 – Redes de Petri Aplicadas à Síntese de Sistemas Digitais
Fim!
§A equação a resolver é:
(0,0,0,1) = (1,0,0,0) + ƒ(σ) °
-1 +1 -1 0
0 –1 +1 +1
n
Grato pela atenção!
Tendo como solução: ƒ(σ) = (1,1)
n
n
Correspondendo a σ1 = t1t2 ou σ2 =t2t1
Nenhuma transição está habilitada em M0.
n
Norian Marranghello – 2003 – Redes de Petri Aplicadas à Síntese de Sistemas Digitais
Norian Marranghello – 2003 – Redes de Petri Aplicadas à Síntese de Sistemas Digitais
2