Exemplo
Equivalência Forte de Programa
Monolítico
• Dados 2 programas, determinar se são
equivalentes fortemente.
Q
R
Equivalência de programa monolítico
• Passo 1: Transformar os fluxos em instruções
rotuladas compostas;
• Passo 2: Identificação dos ciclos infinitos dos
programas;
• Passo 3: União disjunta dos ciclos infinitos;
• Passo 4: Verificar se (I, 1) ≡ (I, 8), se sim Q ≡ R
então B0 = {(1,8)};
• Passo 5: Construção dos conjuntos sucessores:
(B k+1).
• Passo1: Transformar Q e R em instruções
rotuladas compostas e simplificadas:
Q
1:
2:
3:
4:
5:
6:
ω:
R
(G,2),(F,3)
(G,2),(F,3)
(F,4),(G,5)
(F,4),(G,5)
(F,6), (ciclo, ω)
(parada, ), (ciclo, ω)
(ciclo, ω), (ciclo, ω)
8: (G,9),(F,10)
9: (G,9),(F,10)
10: (F,10),(G,11)
11: (F,12), (ciclo, ω)
12: (parada, ), ciclo,ω)
13: (ciclo, ω), (ciclo, ω)
• Passo 2: Identificação dos ciclos infinitos.
• Ciclo infinito de Q
A0 = {}
A1 = {6, }
A2 = {5, 6, }
A3 = {3, 4, 5, 6, }
A4 = {3, 4, 5, 6, }
A5 = {1, 2, 3, 4, 5, 6, }
A6 = {1, 2, 3, 4, 5, 6, }
Portanto: lim Ak = {1, 2, 3, 4, 5, 6 , }
( IR , 7) = (I, ω), pois 7  lim Ak
• Ciclo infinito de R.
A0 = {}
A1 = {12, }
A2 = {11, 12, }
A3 = {10, 11, 12, }
A4 = {8, 9, 10, 11, 12, }
A5 = {8, 9, 10, 11, 12, }
Portanto: lim Ak = {8, 9, 10, 11, 12 , }
( IR , 13) = (I, ω), pois 13  lim Ak
• Passo 3: (Passo 1 algoritmo) União disjunta
dos programas
1:
2:
3:
4:
5:
6:
(G,2),
(F,3)
(G,2),
(F,3)
(F,4),
(G,5)
(F,4),
(G,5)
(F,6),
(ciclo, ω)
(parada, ), (ciclo, ω)
8:
9:
10:
11:
12:
ω:
(G,9),
(F,10)
(G,9),
(F,10)
(F,10),
(G,11)
(F,12),
(ciclo, ω )
(parada, ), (ciclo, ω )
(ciclo, ω ), (ciclo, ω )
• Passo 4: Verificar se (I, 1) ≡ (I, 8), se sim temos
que Q ≡ R e B0 = {(1,8)}
• Passo 5: Construção dos conjuntos sucessores
(Bk + 1)
B1 = {(2, 9), (3, 10)}
B2 = {(4, 10), (5, 11)}
B3 = {(6, 12), (ω, ω)}
B4 = {(, )}
B5 = Ø
– Dúvidas???