|
Ti riferisci al metodo "Paul Unger Esteso" per le macchine non completamente specificate? Sono abbastanza sicuro che non lo chieda mai all'esame, sulle slide non è neanche spiegato chiaramente e l'unico esempio riportato non è neanche tanto sulla parte finale chiaro, sospetto che qualcosa sia stato tagliato anni prima dalle slide originali.
Anch'io ho faticato un pò a capire come si costruisse questa Famiglia degli Insiemi Massimi, cercando su internet ho trovato dei metodi molto più complessi e tutt'ora non sono del tutto convinto °°
Proviamo a considerare lo stesso esempio riportato e la tabella delle implicazioni ricavata sulla slide 49. Il procedimento potrà sembrarti lunghissimo, ma ti assicuro che in realtà è una stupidaggine, è solo molto ma molto ricorsivo.
Le coppie compatibili ricavate sono: (AB ),(AC),(AE),(BC),(CD),(CE), (DE).
Citando il testo:
Si prendono in esame ordinatamente tutti gli stati della macchina e, per ciascuno di essi (q):
1) Si aggiungono ad F tutte le coppie di compatibilità di q;
2) q viene confrontato con tutti gli stati di ciascun elemento E di F e se compatibile con tutti, E si accresce di q, se compatibile solo con alcuni, si genera un nuovo elemento di F
3) si eliminano da F gli elementi inclusi in altri
Partiamo dal considerare F come insieme nullo e aggiungiamo gli elementi uno alla volta.
Cominciamo a prendere in esame lo stato A.
A-1) Aggiungiamo ad F (che all'inizio è nullo) tutte le coppie di compatibilità di A, quindi
F = {(AB ),(AC),(AE)}
A-2) Confrontiamo A con tutti gli stati di ogni elemento di F.
A è compatibile con AB? Naturalmente sì, c'è già A dentro! Dovremmo quindi aggiungere A in AB e ottenere così (AAB ), ma sarebbe ovviamente ridondante, quindi AB rimane inalterato.
Altrettanto vale per (AC) e (AE)
A-3) Al momento abbiamo ottenuto ancora F = {(AB ),(AC),(AE)}. Non ci sono elementi inclusi in altri, quindi non c'è niente da eliminare.
Andiamo avanti con lo stato B.
B-1) Aggiungiamo ad F tutte le coppie di compatibilità di B, ovvero (AB ) e (BC). Si ottiene quindi
F = {(AB ),(AC),(AE), (AB ), (BC)} ---> F = {(AB ),(AC),(AE),(BC)}
B-2) Confrontiamo B con tutti gli stati di ogni elemento di F.
B è compatibile con AB, ma aggiungerlo in AB non avrebbe senso, c'è già.
B è compatibile con AC? Sì, perchè B è compatibile sia con A che con C, quindi dobbiamo aggiungere B in AC e si ottiene (ABC).
B è compatibile con AE? No, perchè anche se B è compatibile con A abbiamo visto dalla tabella che non è compatibile con E. Quindi creiamo un nuovo elemento B che si aggiunge in F.
B è compatibile con (BC)? Ovviamente sì, ma è inutile aggiungerlo visto che è già nella coppia.
Quindi finora abbiamo ottenuto F = {(AB ),(ABC),(AE),(BC), (B )}
B-3) Ora si devono eliminare gli elementi inclusi in altri. E' evidente che vanno eliminati (AB ),(BC) e (B ), visto che sono tutti inclusi in (ABC).
Quindi rimane solo F = {(ABC),(AE)}
Andiamo avanti con lo stato C.
C-1) Aggiungiamo ad F tutte le coppie di compatibilità di C, ovvero (AC), (BC), (CD), (CE). Si ottiene
F = {(ABC),(AE), (AC), (BC), (CD), (CE)}
C-2) Confrontiamo C con ogni elemento di F.
C è compatibile con (ABC)? Ovviamente sì, ma è inutile aggiungerlo in ABC, visto che c'è già.
C è compatibile con AE? Sì, perchè è compatibile sia con A che con E, quindi AE diventa (ACE).
Anche (AC) (BC), (CD), (CE) rimangono inalterati, hanno già C al loro interno.
Quindi, finora abbiamo ottenuto:
F = {(ABC),(ACE), (AC), (BC), (CD), (CE)}
C-3) A questo punto, eliminiamo gli elementi inclusi in altri. (AC) e (BC) sono inclusi in (ABC), mentre (CE) è incluso in (ACE), quindi si eliminano.
F = {(ABC),(ACE), (CD)}
Andiamo avanti con lo stato D.
D-1) Aggiungiamo ad F tutte le coppie di compatibilità di D, ovvero (CD) e (DE). CD è già all'interno di F, quindi basta aggiungere DE.
F = {(ABC),(ACE), (CD), (CE), (DE)}
D-2) Confrontiamo D con ogni elemento di F.
D è compatibile con ABC? No, perchè D non è compatibile con A e B. Quindi dobbiamo aggiungere l'elemento (D) all'insieme F.
D è compatibile con ACE? No, perchè D è incompatibile con A (dovremmo in teoria aggiungere ancora D a F, ma è ovvio che basta farlo una volta).
D è compatibile con CD? Sì, ma è già all'interno di CD e non ha senso aggiungerlo.
D è compatibile con CE? Sì, quindi si deve aggiungere D a CE, che diventa così (CDE).
D è compatibile con DE? Sì, ma è già all'interno di DE e non ha senso aggiungerlo.
Quindi F è diventato F = {(ABC),(ACE), (CD), (CDE), (DE), (D)}
D-3) Eliminiamo gli elementi inclusi in altri. CD, DE e D sono tutti inclusi in CDE, quindi si eliminano e rimane
F = {(ABC),(ACE),(CDE)}
Terminiamo con lo stato E.
E-1) Aggiungiamo a F ogni coppia compatibile con E, cioè (AE), (CE) e (DE). Si ottiene:
F = {(ABC),(ACE), (CDE), (CE), (DE)}
E-2) Confrontiamo E con ogni elemento di F.
E è compatibile con ABC? No, perchè E non è compatibile con B. Quindi si dovrà aggiungere (E) all'insieme F.
E è compatibile con (ACE)? Ovviamente sì, ma non accade nulla.
Altrettanto vale per (CDE), (CE), (DE).
Quindi si ottiene:
F = {(ABC),(ACE), (CDE), (AE), (CE), (DE), (E)}
E-3) Si eliminano gli elementi presenti in altri. (AE), (CE) ed (ED) sono inclusi in (ACE), inoltre si ha anche che (CE), (DE) ed (E) sono inclusi in (CDE), quindi si eliminano e rimane:
F = {(ABC),(ACE), (CDE)}
Questo è il risultato a cui sono giunto applicando alla lettere l'algoritmo riportato sulla slide.
Se osservi il Grafo di Compatibilità riportato nell'ultima slide (il pentagono, insomma), i cui nodi sono gli stati A,B,C,D,E, collegati a seconda degli stati condizionanti, noterai che (ABC),(ACE), (CDE) sono proprio i "triangoli" che lo compongono per intero.
|
Preferiti: 0
