Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
DISCRETE EVENT SYSTEMS
OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DES
Redazione a cura del Dr. Ing. Francesco Liberati ([email protected])
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
INDICE DELLA LEZIONE
OPERATORI SU AUTOMIOPERATORI UNITARI;
PRODOTTO DI AUTOMI;
PARALLELO DI AUTOMI.
LINGUAGGI REGOLARI
OSSERVATORI
DIAGNOSERS
VALIDAZIONE FORMALE
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
CI PROPONIAMO DI STUDIARE ALCUNE DELLE PIU’ COMUNI OPERAZIONI ATTUABILI SU:
1. SINGOLI AUTOMI:
PARTE ACCESSIBILE DI UN AUTOMA;
PARTE COACCESSIBILE.
2. DUE O PIU’ AUTOMI:
PRODOTTO DI AUTOMI;
PARALLELO DI AUTOMI.
INTRODUZIONE
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
OPERATORI SU SINGOLI AUTOMI (cont.)Parte accessibile:L’OPERATORE PARTE ACCESSIBILE RIMUOVE DALL’AUTOMA G TUTTI GLI STATI (E RELATIVE TRANSIZIONI) NON RAGGIUNGIBILI DA x0.
ESEMPIO:
Acc(G)
NESSUNA INFLUENZA SU ED ; )(GL )(GLm
AUTOMA ACCESSIBILE. )(GAccG
.
.
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
OPERATORI SU SINGOLI AUTOMIParte co-accessibile:L’OPERATORE PARTE CO-ACCESSIBILE RIMUOVE DALL’AUTOMA G TUTTI GLI STATI (DETTI NON CO-ACCESSIBILI) PARTENDO DAI QUALI NON E’ POSSIBILE RAGGIUNGERE UNO STATO MARCATO:
CoAcc(G)
NESSUNA INFLUENZA SU ; )(GLmAUTOMA CO-ACCESSIBILE. )(GcoAccG .
.
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
OPERATORI DI COMPOSIZIONE(PRODOTTO/PARALLELO DI AUTOMI)
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
PRODOTTO DI AUTOMISI TRATTA DI UN OPERATORE DI FORTE SINCRONIZZAZIONE TRA AUTOMI. IL PRODOTTO DI DUE AUTOMI E’ UN AUTOMA “MULTIVARIABILE”, COMPOSIZIONE DEI DUE AUTOMI, IN CUI SI CONSENTONO SOLO LE TRANSIZIONI NEGLI AUTOMI OPERANDI CHE SONO ETICHETTATE DA STESSI EVENTI (FORTE SINCRONIZZAZIONE). ES:
x y
z
a
c
cb
0 1
2ba
c
0,x 2,y
a
1,z
b
2,x
c
:1G :2G
:21 GG
COME CAMBIANO I LINGUAGGI?
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
PARALLELO DI AUTOMIOPERAZIONE STANDARD DI COMPOSIZIONE TRA AUTOMI. MENO RESTRITTIVA RISPETTO
ALLA MOLTIPLICAZIONE. NEL PARALLELO DI DUE AUTOMI: GLI EVENTI COMUNI ( ) VENGONO ESEGUITI SOLO SE ENTRAMBI GLI AUTOMI LI
ESEGUONO IN MANIERA SINCRONA ( ); GLI EVENTI PRIVATI ( ) VENGONO SEMPRE ESEGUITI.
21 EE
)()( 21 xxe
1221 \\ EEEEe
x y
z
a
b
0 1
a
},{1 baE
}{2 aE
0,x 1,y 1,z
a b
0,x 1,y
a
21 ||GG
21 GG
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
SINCRONIZZAZIONE DI AUTOMINEGLI ESEMPI SU CONSIDERATI, UN QUALUNQUE EVENTO COMUNE A DUE O PIU’ AUTOMI ( ) PUO’ RAPPRESENTARE, PER ESEMPIO, LA RICHIESTA DI ACCESSO A UNA RISORSA CONDIVISA. EVENTI PRIVATI POSSONO RAPPRESENTARE INVECE DELLE AZIONI CHE NON VINCOLANO IL COMPORTAMENTO DEGLI AGENTI ESTERNI ALL’AUTOMA.ES: DINING PHILOSOPHERS AND PARALLEL COMPOSITION
21 EEe
free usein
12,11 ff
ff 2,1
think eat
idle
idle
1F1P
11 f 21 f
21 f 11 f
f1
L’INTERAZIONE TRA DUE FILOSOFI PUO’ ESSERE DESCRITTA DALL’AUTOMA:
2||2||1||1 PFPFDF L’AUTOMA E’ BLOCCANTE
)(|| DFcoAccControllerDF SINTESI DEL
CONTROLLORE
ForchettaFilosofo
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
LINGUAGGI REGOLARI(PROBLEMI PRATICI DI MODELLAZIONE)
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
CONSIDERAZIONI SULLA MODELLAZIONEI DES (CIOE’ I SISTEMI CHE INTENDIAMO MODELLARE E CONTROLLARE) SONO CARATTERIZZATI DA LINGUAGGI. COSTRUIRE AUTOMI CHE GENERANO LINGUAGGI (CIOE’ MODELLIZZANO QUEL SISTEMA) E MARCANO LINGUAGGI (CIOE’ RICONOSCONO TASK SPECIFICI) E’ PIU’ AGEVOLE RISPETTO A LAVORARE DIRETTAMENTE SUI LINGUAGGI.
PER OGNI LINGUAGGIO ESISTE UN AUTOMA CHE GENERA/MARCA QUEL LINGUAGGIO.
LA QUESTIONE DI INTERESSE PRATICO E’:PER OGNI LINGUAGGIO, ESISTE UN AUTOMA FINITO CHE GENERA/MARCA QUEL
LINGUAGGIO?
LA RISPOSTA E’ NO.
LE RETI DI PETRI CONSENTONO DI RAPPRESENTARE ALCUNI LINGUAGGI NON REGOLARI
Def. (Linguaggio regolare): UN LINGUAGGIO E’ DETTO REGOLARE SE PUO’ ESSERE MARCATO DA UN AUTOMA A STATI FINITI. R E’ LA CLASSE DEI LINGUAGGI REGOLARI.
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
MODELLI MINIMI (approfondimento)IN GENERE, PIU’ AUTOMI MARCANO UNO STESSO LINGUAGGIO REGOLARE. SIAMO INTERESSATI A TROVARE L’AUTOMA CARATTERIZZATO DA MINIMO SPAZIO DI STATO (DETTO RICONOSCITORE CANONICO).
SOTTO BLANDE IPOTESI, IL RICONOSCITORE CANONICO E’ UNICO.
UN AUTOMA NON MINIMO E’ CARATTERIZZATO DALLA PRESENZA DI STATI EQUIVALENTI.
))(())(( 2121 xGLxGLsexx mm
Def. (Stati equivalenti): DUE STATI DI UN AUTOMA G SONO DETTI EQUIVALENTI SE:
CIOE’ STATI DA CUI E’ POSSIBILE RAGGIUNGERE STESSI STATI MARCATI. IL RICONOSCITORE CANONICO PUO’ ALLORA ESSERE OTTENUTO DAPPRIMA INDIVIDUANDO, QUINDI AGGREGANDO TUTTI GLI STATI EQUIVALENTI.
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
AUTOMI OSSERVATORI DI DES
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
OSSERVATORIIN ASSENZA DI
INCERTEZZE/IMPERFEZIONI DI MODELLAZIONE, L’OSSERVAZIONE DI UN MODELLO DETERMINISTICO DEL DES ASSICUREREBBE PIENA INFORMAZIONE RIGUARDO LO
STATO. NELLA REALTA’ OCCORRE CONSIDERARE MODELLI NON
DETERMINISTICI.
SI PONE ALLORA IL PROBLEMA DI COSTRUIRE UN AUTOMA DETERMINISTICO (OSSERVATORE) CHE STIMI LO STATO DEL DES IN ESAME (MODELLIZZATO DA UN
AUTOMA NON DETERMINISTICO).
E’ UTILE IN TAL CASO DARE UN NOME ANCHE AGLI EVENTI INOSSERVABILI (INVECE DI
ETICHETTARLI CON ).INFATTI, SPESSO QUESTI EVENTI
SONO CONOSCIUTI (E.G. GUASTI).
unObsobs EEE
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
OSSERVATORI (cont.: esempio)
},,{ vueE dunObs AUTOMA OSSERVATORE DETERMINISTICO
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
EVENT DIAGNOSIS
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
DIAGNOSI DI EVENTIESAMINANDO GLI EVENTI
(OSSERVABILI) ACCADUTI, E’ POSSIBILE DECIDERE SE UN DATO
EVENTO INOSSERVABILE (ES. GUASTO) E’ ACCADUTO O MENO?
SI PONE ALLORA IL PROBLEMA DI COSTRUIRE UN AUTOMA DETERMINISTICO ETICHETTATO (DIAGNOSER) CHE DECIDA (OVE POSSIBILE) SE UN DATO EVENTO
INOSSERVABILE E’ ACCADUTO O MENO.
L’IDEA CHIAVE E’ CHE, COME ANCHE SI EVINCE DALLO STUDIO DEGLI
OSSERVATORI, ALL’AUMENTARE DEGLI EVENTI OSSERVATI DIMINUISCE
L’INCERTEZZA SULLO STATO DEL SISTEMA
(PROBLEMA DELLA DIAGNOSTICABILITA’DI UN EVENTO INOSSERVABILE)
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
DIAGNOSI DI EVENTI (cont.: esempio)
},,{ vueE dunObs
DIAGNOSER DETERMINISTICO DELL’EVENTO de
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
FORMAL VERIFICATION AND MODEL CHECKING(SAFETY, BLOCKING, DIAGNOSABILITY)
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
FORMAL VERIFICATIONSVILUPPO DI PROCEDURE FORMALI PER LA VALIDAZIONE DI PROTOTIPI HARDWARE E SOFTWARE (ES: CIRCUITI INTEGRATI, PROTOCOLLI DI COMUNICAZIONE,...). OCCORRE ASSICURARE CHE IL PROTOTIPO ESIBISCA SEMPRE UN COMPORTAMENTO ACCETTABILE (NON BANALE NEL CASO DI SISTEMI COMPLESSI, CON MIGLIAIA/MILIONI DI COMPONENTI). VENGONO TESTATE UNA SERIE DI PROPRIETA’. AD ESEMPIO:
1. SAFETY: PROBLEMA DELLA RAGGIUNGIBILITA’ DI STATI INDESIDERATISTUDIO DI ACCESSIBILITA’ SUL PARALLELO DEI COMPONENTI DEL SISTEMA COMPLESSIVO;
2. BLOCKING: STUDIO DI CO-ACCESSIBILITA’ SUL PARALLELO DEI COMPONENTI DEL SISTEMA COMPLESSIVO. E’ ANCHE POSSIBILE INDIVIDUARE GLI EVENTUALI DEADLOCKS/LIVELOCKS (STATI NON CO-ACCESSIBILI);
3. DIAGNOSTICABILITA’
ALGORITMI EFFICIENTI CHE RESTITUISCONO UNA RISPOSTA POSITIVA, OPPURE UN CONTROESEMPIO NEGATIVO.
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE I3OPERAZIONI SUGLI AUTOMI ED ANALISI DELLE PROPRIETA’ DEI DESDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Consigliati:[1] Cassandras, Lafortune, Introduction to Discrete Event Systems, Second Edition, Springer Editore. Capitolo 2 (Languages and Automata);
PER APPROFONDIRE
Top Related