1 Modellazione di sistemi
1. Si modelli mediante unsistema di transizioni ilsistema ostituito daun
elasti o, he inizialmente non e teso e he puo essere teso e rilas iato
unnumero indeterminato di volte. Puoa adere he aun erto punto,
quandovienerilas iato,siroviniosirompaenonsiapiupossibiletenderlo
dinuovo. Sirappresentilospaziodeglistati orrispondente.
2. Si modelli mediante unsistema di transizioni ilsistema ostituito daun
semaforoil ui olorepuopassare dal verde algiallo, dal gialloal rosso
e dal rosso al verde. Il semaforo puo restare dello stesso oloreper un
numero inde nito di stati. Nello stato iniziale il semaforo e rosso. Si
rappresentiil orrispondentespaziodeglistati.
3. Simodi hiilmodellodell'eser iziopre edente,aggiungendolapossibilita
he,inqualunquemomento,arriviunvei oloalsemaforo,assumendo he
ivei olirispettinosempreil odi estradale.
Come garantire he i vei oli giunti al semaforo non rimangano l per
sempre?
4. De nire un sistema di transizioni he modelli il omportamento di un
semaforoin uian heilpassaggiodalrossoalverdeesegnalatodalgiallo.
5. Modellare mediante un sistema di transizioni il sistema di gestione di
una oda, di dimensione massima nita, ostituito da due pro essi he
eseguonoiseguentiprogrammi:
P1:
Q:=empty_queue; P2:
n:=0; while true do
while not(full(Q)) do await not(empty(Q));
n:=n+1; m:=dequeue(Q);
enqueue(n,Q) serve(m)
done done
Rappresentare una parte dello spazio degli stati orrispondente a tale
sistema,assumendo heladimensionemassimadella odasia3.
6. Sempli areil modellodell'eser iziopre edente,assumendo henoninte-
ressiil \nome"deglielementiin oda,ma soltantoil numerodielementi
hesonopresentinella oda. Rappresentareil orrispondentespaziodegli
stati,sempreassumendo heladimensionemassimadella odasia3.
1. Dare dimostrazioni semanti he delle seguenti proprieta degli operatori
temporali
3eun asoparti olaredi U: 3A $ >UA
3e2sonointerde nibili: 2A $ :3:A
3A $ :2:A
Poi heeri essivaetransitiva: j=2A!A
j=A!3A
j=2A!22A
ProprietadelNEXT j=2A!
A
j=
A!3A
A $ :
:A
:
A $
:A
j=
(A!B)!(
A!
B)
ProprietadelBOX: j=2(A!B)!(2A!2B)
j=A^2(A!
A)!2A
2A $ A^
2A
ProprietadelDIAMOND: 3A $ A_
3A
Proprietadi UNTIL: j=AUB !3B
AUB $ B_(A^
AUB)
2. Dareunadimostrazionesemanti adellaseguenteequivalenza:
:(AUB) $ 2:B_(:BU(:A^:B))
3. Si onsideriil sistema dell'eser izio3del paragrafo1eformulareinLTL
laproprieta heseunvei oloarrivaalsemaforo,primaopoipassera.
4. Si onsideriil sistema dell'eser izio6del paragrafo1eformulareinLTL
leseguentiproprieta:
se in qualsiasi istante la oda e vuota, allora la oda onterra un
elementonellostatosu essivo;
sein qualsiasiistantela oda ontiene 3elementi, alloranellostato
su essivola oda onterra2elementi;
seinqualsiasiistantela oda ontiene 1o2elementi,alloraprimao
poila odasaravuotao onterra1soloelemento.
3 Tableaux per LTL
1. Dimostraremediantetableauxlavaliditadelleformuleriportateapagina
122dellibrodiPeled.
2. Costruireuntableau ompletoper ias unodeiseguentiinsiemidiformule
e an ellarne i nodi hiusi. Nel asoin ui la radi e non sia an ellata,
identi arei amminiaperti nel tableaux ed estrarreda ias unodi essi
(b) 32p; 32:p
( ) 23p; 32:p
(d) pUq; 2:q
(e) pUq; 2:p
(f) (
p)Uq; :3(p^q)
(g) 2(green!(greenUyellow); 3(green^
red)
(h) 2(green!(greenUyellow); 3(green^
(:green^:yellow))
(i) 2(yellow_(red_greenUyellow)); 3(red^
green)
(j) 2(yellow_(red_greenUyellow)); 2:yellow
(k) 2(yellow_(red_greenUyellow)); 23:yellow
(l) 2(
openopen_pull); :open; 3open
4 Automi
1. SiaAl'automa eti hettato daformule, ostituitodaS =fs1;s2;s3g on
= f(s1;s1);(s1;s2);(s2;s1);(s2;s3);(s3;s3)g, I = fs1g, F = fs3g, e
L(s1)=p,L(s2)=q^:r,L(s3)=(p_q)^r. Costruireil orrispondente
automaeti hettato dasottoinsiemi diP =fp;q;rg.
2. Costruireunautomadi Bu hi sempli eper ias uno deiseguentiautomi
generalizzatiA=h;S;;I;L;Fi.
(a) S = fs1;s2;s3g, = f(s1;s1);(s1;s2);(s2;s1);(s2;s3);(s3;s3)g,
I =fs1g, F =ffs1g;fs3gg,eL(s1) =p,L(s2) =q^:r, L(s3)=
p_q.
(b) S =fs1;s2;s3g,
= f(s1;s1);(s1;s2);(s2;s2);(s2;s3);(s3;s3);(s3;s1)g, I = fs1g,
F =ffs1g;fs2g;fs3gg,eL(s1)=fpg,L(s2)=fqg,L(s3)=frg.
3. Costruirel'unione el'intersezionedegliautomi:
(a) A onS=fs1;s2;s3g,
= f(s1;s1);(s1;s2);(s2;s2);(s2;s3);(s3;s3);(s3;s1)g, I = fs1g,
F =fs1;s3g,eL(s1)=p^q,L(s2)=p_r, L(s3)=:q^:r.
(b) B onS 0
=fq1;q2g, 0
=f(q1;q2);(q2;q1);(q2;q2)g,I 0
=S 0
, F 0
=
fq1g,L 0
(q1)=:p,L 0
(q2)=q_r.
5 Veri a
1. Costruireunautoma orrispondentea ias unadelleformuledell'eser izio
2delparagrafo3.
2. Per ias uno dei punti seguenti, veri are se il sistema rappresentato
dall'automaA=h;S;;I;L;FisoddisfalaformulaSpe .
23giorno.
(b) Stesso automa del punto pre edente, ma on F = fs2g. Stessa
formuladelpuntopre edente.
( ) Stessoautoma delpunto(2a),ma onF =fs1g. Stessaformuladel
punto(2a).
(d) Automa generalizzato des ritto ome al punto (2a), ma on F =
ff
1
;f
2
g,dovef
1
=fs1g;f
2
=fs2g. Stessaformuladelpunto2a.
(e) Stessoautomadel puntopre edente. Spe =2:(giorno^notte).
(f) S =fs1;s2;s3g, =f(s1;s2);(s2;s1);(s2;s3);(s3;s3)g,I =fs1g,
L(s1)=:extended^:malfun tion,L(s2)=extended^:malfun tion,
L(s3) = extended^malfun tion, F =S. Spe = 2(extended !
:extended)
3. Si onsideriil modellodelsistema2del paragrafo1.
(a) Veri areseil sistemasoddisfalaspe i a23verde.
(b) Siaggiungaalmodelloilvin olodifairness heri hiede heleese u-
zionipassinoperunostatoin uieveroverdein nitamente spesso.
Veri areseil sistemasoddisfa23rosso.
Eser izio2 del paragrafo 2. Perdimostrare
:(AUB) $ 2:B_(:BU(:A^:B))
mostriamo heperogniinterpretazioneMestatok:
1. SeM
k
j=:(AUB),alloraM
k
j=2:B_(:BU(:A^:B)). Assumiamo
dunqueM
k
j= :(AUB), ioeM
k
6j=(AUB): e falso he esiste n k
tale heM
n
j=B eperognii,ki<n,M
i j=A.
Quindi: ( aso1)nonesistenktale heM
n
j=B,oppure( aso2)esiste
nk tale heM
n
j=B,maper ias unoditalinsiha henonperogni
i,ki<n,M
i j=A.
Nel aso1, per ognin k, M
n
6j= B, quindi M
k
j=2:B e amaggior
ragioneM
k
j=2:B_(:BU(:A^:B)).
Nel aso 2, sia n il piu pi olo intero maggiore o uguale a k tale he
M
n
j=B,per uisihaM
n
j=B e:
(?) perognii,ki<n: M
n
6j=B, ioeM
n j=:B
Perl'ipotesidel aso2,sihaan he henonperognii,ki<n,M
i j=A,
ioeesistem,km<n,tale heM
m
6j=A. Poi hekm<n,per(?),
sihaan heM
m
j=:B,quindiM
m
j=:A^:B. Inoltre,sempreper(?),
perognii,ki<m, M
i
j=:B. QuindiM
k
j=(:BU(:A^:B)),ea
maggiorragioneM
k
j=2:B_(:BU(:A^:B)).
Poi heinentrambii asipossibilisihaM
k
j=2:B_(:BU(:A^:B)),
nesegue he omunqueM
k
j=2:B_(:BU(:A^:B)).
2. SeM
k
j=2:B_(:BU(:A^:B))alloraM
k
j=:(AUB). Assumiamo
M
k
j=2:B_(:BU(:A^:B)), ioesiveri aunodeidue asiseguenti:
( aso 1) M
k
j=2:B. Inquesto asoovviamenteM
k
6j=AUB,quindiM
k j=
:(AUB).
( aso 2) M
k
j=(:BU(:A^:B)):
(?) esiste nk tale he M
n
j=:A^:B e per ognii, ki <n,
M
i 6j=B.
Se fosse (per assurdo) M
k
j=AUB, dovrebbeesistere m k tale
heM
m
j=B etale he
(??) perognii,ki<m, M
i j=A.
Ovviamentemdovrebbeesserestrettamente maggioredin,per(?),
quindi sarebbe k n < m, e per (??), si avrebbe M
n j= A,
ontraddi endoM
n
j=:A^:B.
Quindil'ipotesiM
k
j=AUBeassurda,esihaan hein questo aso
M
k
j=:(AUB).
Poi hein entrambi i asi possibili si ha M
k
j= :(AUB), ne segue he
omunqueM
k
j=:(AUB).
