facoltà di ingegneria corso di laurea: insegnamento: lezione n°: titolo: docenti: ingegneria...
TRANSCRIPT
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
DISCRETE EVENT SYSTEMS
LINGUAGGI FORMALI ED AUTOMI
Redazione a cura del Dr. Ing. Francesco Liberati ([email protected])
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
INDICE DELLA LEZIONE
INTRODUZIONE AI LINGUAGGI FORMALI.
LINGUAGGI FORMALI
ALFABETO, PAROLE, LINGUAGGI;
OPERAZIONI SUI LINGUAGGI.
AUTOMI
LINGUAGGI GENERATI E MARCATI;
EQUIVALENZA TRA AUTOMI;
BLOCKING.
BIBLIOGRAFIA
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
CI PROPONIAMO DI STUDIARE IN MANIERA FORMALE IL COMPORTAMENTO LOGICO DEI DES (UNTIMED LENGUAGES). OSSERVAZIONI:
1. PER UN DES DETERMINISTICO, NOTO LO STATO INIZIALE ED UNA SEQUENZA DI EVENTI, RISULTA UNIVOCAMENTE DETERMINATA LA TRAIETTORIA DELLO STATO;
2. TUTTE LE POSSIBILI SEQUENZE DI EVENTI (LINGUAGGI) SONO GENERATE A PARTIRE DALL’INSIEME DEGLI EVENTI E (ALFABETO).
INTRODUZIONE
INSIEME DI POSSIBILI SEQUENZE DI EVENTI
(LINGUAGGI)
MODELLI DIFFERENZIALI
DES CVDS
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
PAROLAPRESO UN DES, L’INSIEME DEGLI EVENTI E COSTITUISCE UN ALFABETO, UNA QUALUNQUE SEQUENZA DI EVENTI IN E FORMA UNA PAROLA.
Def. (Parola): CONSIDERATO UN DES E L’INSIEME DEGLI EVENTI E AD ESSO ASSOCIATO, UNA PAROLA (ANCHE: STRINGA, TRACCIA) DEFINITA SU E E’ UNA QUALUNQUE SEQUENZA (FINITA O NON FINITA) DI EVENTI IN E.
ES:
LA LUNGHEZZA DI UNA PAROLA È DATA DAL NUMERO DI LETTERE (EVENTI) CONTENUTE NELLA PAROLA.
)(,...,,:},,{ alfabetoognisudefinitavuotastringabacbaabcParolecbaE
)0|(||:| econvenzionpersstringalunghezzas
sstringanellaeeventodellfrequenzas e ':||
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
PRIME OPERAZIONI FONDAMENTALIChiusura di Kleene:DATO UN INSIEME DI EVENTI E, LA CHIUSURA DI KLEENE DI E, INDICATA CON E ,E’ L’INSIEME DI TUTTE LE PAROLE DI LUNGHEZZA FINITA GENERABILI A PARTIRE DAGLI EVENTI IN E.
QUINDI:CON DENOTIAMO UNA GENERICA PAROLA GENERATA DA E.
Concatenazione di due Parole:
*
*Es
,),(,,: **** sttsconcEtsEEEconc DOVE st È LA STRINGA COSTITUITA DAGLI EVENTI IN s IMMEDIATAMENTE SEGUITI DAGLI EVENTI IN t.
*321321 ,,, Esssconssss
PREFISSO SUFFISSOSOTTOSTRINGA
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
LINGUAGGIOPRESO UN DES, L’INSIEME DEGLI EVENTI E COSTITUISCE UN ALFABETO, UNA QUALUNQUE SEQUENZA DI EVENTI IN E UNA PAROLA (STRINGA, TRACCIA), UN INSIEME QUALUNQUE DI POSSIBILI PAROLE UN LINGUAGGIO.
Def. (Linguaggio): UN LINGUAGGIO L DEFINITO SU UN INSIEME DI EVENTI E E’
UN INSIEME DI SEQUENZE FINITE DI EVENTI IN E. SI HA: .
COME DEFINIRE UN LINGUAGGIO:
1. DEFINIZIONE ENUMERATIVA (SI ELENCANO TUTTE LE PAROLE CONTENUTE NEL LINGUAGGIO). POSSIBILE PER LINGUAGGI FINITI. ES:
2. DEFINIZIONE VERBALE/INSIEMISTICA:
3. AUTOMI E MODELLI.
*EL
},,,,,{},,{ 1 abcaacbaLcbaE
}{}2|:|{ * bperfinisconochefinitalunghezzadistringheletutteLsEsL
vuotolinguaggio
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
OPERAZIONI SUI LINGUAGGIConcatenazione di due linguaggi:
Prefix-clousure:
Kleene-clousure:
},,:{),(, **BABABABA LbLaabsEsLLLLconcELL
DEFDEF
},:{ *** LstEtEsLELDEF
LLLLLLLLLLLELDEF
}{**
….
Substring-clousure;
Suffix-clousure ;
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
OPERATORI DI PROIEZIONE NATURALEProiezione di stringhe:
**: AP EEP PP EeEsforePsPseP ,)()()( * )(P
AP EEeif \
AEeife )(eP
PROIEZIONE EVENTO NULLO
PROIEZIONE EVENTO
PROIEZIONE STRINGA
LA PROIEZIONE DA UN INSIEME DI EVENTI DI PARTENZA AD UN INSIEME DI
EVENTI DI ARRIVO , ASSOCIA AD UNA GENERICA PAROLA IN LA PAROLA
PIU’ “SIMILE” IN (OTTENUTA CANCELLANDO DALLA PAROLA GLI EVENTI NON
CONTENEUTI IN . ).
*PE
*AE
*PE
*AE
AE})(:{)(2: *1*1 *
tsPEstPEP PE
AP (Proiezione inversa)
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
OPERATORI DI PROIEZIONE NATURALE (cont.)Proiezione di linguaggi:
})(,:{)( ** stPLtEsLPEL AP
LA PROIEZIONE DI UN LINGUAGGIO SI OTTIENE SEMPLICEMENTE PROIETTANDO
LE PAROLE CONTENUTE NEL LINGUAGGIO.
Alcune proprietà delle proiezioni:
))(())(( 11 LPPLLLPP
)()()()()()( BPAPBAPBPAPBAP
)()()()()()( 111111 BPAPBAPBPAPBAP
)()()()()()( 111 BPAPABPBPAPABP
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
MODELLI AD EVENTI DISCRETI: AUTOMATA
(RAPPRESENTARE/GENERARE I LINGUAGGI)
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
AUTOMATACOME VISTO, L’ENUMERAZIONE E LA DESCRIZIONE LINGUISTICA/INSIEMISTICA SONO DEI METODI IMMEDIATI PER DESCRIVERE I LINGUAGGI FORMALI.
GLI AUTOMI INVECE SONO DELLE STRUTTURE CHE GENERANO LINGUAGGI SECONDO DELLE REGOLE SPECIFICATE.
Esempio (Diagrama di Transizione degli Stati):
},,{ zyxX
},,{ cbaE
x
z
y
a,b
a
ba
STATO INIZIALE
STATO MARCATO
xazfyaxf
Es
XEXf
etransiziondiFunzione
),(),(
:
:
:
OSSERVAZIONI:
1. c EVENTO NON
ATTIVO;
2. ;
3. ;
4. . (PER UN DATO
STATO, NON TUTTI I VALORI DELLA
FUNZIONE f SUL PRODOTTO X x E SONO
DEFINITI. AD ESEMPIO, f(z,b) NON E’
DEFINITO).
yayf ),(},,{ cbaE
ybxfaxf ),(),(
parzialefunzionef
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
AUTOMATA (cont.)Def. (Automa): UN AUTOMA DETERMINISTICO, DENOTATO CON G, E’ UNA SESTUPLA:
DOVE:
1. E’ L’INSIEME DEGLI STATI ASSOCIATI A G;
2. E’ L’INSIEME DEGLI EVENTI ASSOCIATI A G;
3. E’ LA FUNZIONE DI TRANSIZIONE (FUNZIONE PARZIALE);
4. FUNZIONE EVENTI POSSIBILI:
;
5. STATO INIZIALE;
6. INSIEME DI STATI MARCATI.
),,,,,( 0 mXxfEXG
X
E
XEXf :EX 2:
0x
XXm
}),(:{)( definitoexfEex
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
AUTOMATA (cont.: OSSERVAZIONI)
XEXf :IN COMPUTER SCIENCE LA FUNZIONE E’ IN GENERE COMPLETAMENTE DEFINITA SUL PRODOTTO . EX
L’AUTOMA E’ DETERMINISTICO POICHE’ LA FUNZIONE DI TRANSIZIONE E’ MONODROMA (AD UN PUNTO DELLO SPAZIO DI PARTENZA ASSOCIA UN SOLO PUNTO DELLO SPAZIO DI ARRIVO). NEGLI AUTOMI NON DETERMINISTICI SI HA .
XEXf 2:
DATO UN INSIEME , L’INSIEME , DETTO INSIEME POTENZA DI , DENOTA L’INSIEME DI TUTTI I SOTTOINSIEMI DI .
S S2 SS
IL COMPORTAMENTO LOGICO DELL’AUTOMA E’ IL SEGUENTE: PARTE DALLO STATO INIZIALE E SALTA DI STATO IN STATO A SECONDA DEL VERIFICARSI DEGLI EVENTI. L’INSIEME X PUO’ ESSERE FINITO O INFINITO. GLI STATI MARCATI SONO STATI DI PARTICOLARE INTERESSE E LA LORO DEFINIZIONE DIPENDE DAL PROBLEMA (PROBLEMA DI MODELLISTICA).
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
AUTOMATA E LINGUAGGI
E’ UTILE ESTENDERE LA FUNZIONE DI TRANSIZIONE DALL’INSIEME
ALL’INSIEME
.
EX *EX
*
*
,)),,((),(
),(
:
EsEeesxffsexf
xxf
XEXf
Funzione di transizione estesa:
PARTENDO DA QUESTA GENERALIZZAZIONE DELLA FUNZIONE DI TRANSIZIONE,
E’ IMMEDIATO CAPIRE COME, ED IN CHE SENSO, GLI AUTOMATA GENERANO
LINGUAGGI.
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
LINGUAGGIO GENERATO DA G
Def. (Linguaggio generato): IL LINGUAGGIO GENERATO DA UN AUTOMA G E’
L’INSIEME DELLE STRINGHE PER CUI LA TRANSIZIONE A PARTIRE DALLO STATO
INIZIALE E’ DEFINITA:
}),(:{)( 0* definitosxfEsGL
CIOE’, L(G) DA INFORMAZIONI RIGUARDO L’INSIEME DI TUTTE LE POSSIBILI
TRANSIZIONI NEL DIAGRAMMA DI STATO A PARTIRE DALLO STATO INIZIALE.
Osservazioni importanti:
1. DALLA DEFINIZIONE DI f, SEGUE CHE L(G) E’ PREFIX-CLOSED:
},)),,(({}),({ 00 pesdefinitoepxffdefinitosxf
2. SE f E’ UNA FUNZIONE TOTALE, ALLORA . *)( EGL
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
LINGUAGGIO MARCATO DA G
Def. (Linguaggio segnato): IL LINGUAGGIO SEGNATO DA UN AUTOMA G E’ DATO
DALL’INSIEME DELLE CATENE DI EVENTI CHE CAUSANO UNA TRANSIZIONE
DALLO STATO INIZIALE AD UNO QUALUNQUE DEGLI STATI MARCATI:
}),(:{)( 0*
mm XsxfEsGL
Osservazioni importanti:
1. Lm(G) NON E’ NECESSARIAMENTE PREFIX-CLOSED: SE UN CAMMINO
CONDUCE AD UNO STATO MARCATO, NON E’ DETTO CHE UNA PARTE DELLO
STESSO CAMMINO CONDUCA AD UNO STATO MARCATO (IN GENERALE, NON
TUTTI GLI STATI SONO MARCATI);
2. SI DICE CHE L’AUTOMA “RICONOSCE” IL LINGUAGGIO Lm(G);
3. DIVERSI AUTOMI POSSONO GENERARE O SEGNARE GLI STESSI LINGUAGGI;
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
EQUIVALENZA (PER LINGUAGGI) TRA AUTOMI
Def. (Equivalenza per linguaggio): DUE AUTOMI G E G’ SONO EQUIVALENTI (PER
LINGUAGGIO) SE:
)'()()'()( GLGLGLGL mm
ESEMPIO
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
BLOCKING: DEADLOCKS AND LIVELOCKS
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
BLOCCO
PUO’ ACCADERE CHE UN AUTOMA ENTRI IN UNO STATO DAL QUALE POI NON E’
PIU POSSIBILE RAGGIUNGERE UNO STATO MARCATO, E CHE QUINDI NON RIESCA
A COMPIERE IL TASK ASSEGNATO O RAGGIUNGERE LO STATO DESIDERATO.
CIO’ PUO’ ACCADERE IN DUE MODI DIFFERENTI:
)(:\ xXXx m
Deadlock:Livelock:
)}(),({
:\
xeSexfSx
connessofortementeXXS m
xs1
s2
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
BLOCCO (cont.: interpretazione)
SI HA IN GENERALE:
)()()( GLGLGL mm
UN BLOCCO (DEADLOCK O LIVELOCK) SI HA SE E SOLTANTO SE LA SECONDA
INCLUSIONE E’ STRETTA.
Def. (Automa bloccante): UN AUTOMA G E’ DETTO BLOCCANTE (PUO’ CIOE’
INCORRERE IN UNO STATO DI BLOCCO) SE:
)()( GLGLm
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
ESEMPIO (status check di un macchinario)
UN MACCHINARIO ESIBISCE IL SEGUENTE NORMALE COMPORTAMENTO:
1. ALL’ACCENSIONE SEGNALA “MACCHINA ACCESA”;
2. A SEGUITO DELL’ACCENSIONE LANCIA UNA DIAGNOSTICA. SEGUONO DUE
POSSIBILI SEGNALI:
1. “STATO NORMALE”;
2. “STATO DI GUASTO”.
3. TERMINATA LA DIAGNOSTICA SEGNALA “DIAGNOSTICA TERMINATA”.
VOGLIAMO COSTRUIRE UN SEMPLICE AUTOMA CHE, OSSERVANDO IL
SUCCEDERSI DEGLI EVENTI, RICONOSCA LO STATO FINALE A SEGUITO DELLA
DIAGNOSTICA.
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
ESEMPIO (status check di un macchinario)
X=3 E’ LO STATO MARCATO (DIAGNOSTICA CONCLUSA);
L’AUTOMA E’ BLOCCANTE;
L’AUTOMA PROCESSA TUTTI GLI EVENTI POSSIBILI (FUNZIONE DI TRANSIZIONE
TOTALE) ;
X=4 STATO BLOCCANTE DI ERRORE.
0 1
2
2
3 4d
e1
e2
d
d
de1, e2
e1, e2
d,e1, e2
e1, e2
d,e1, e2
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
AUTOMI NON DETERMINISTICI
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
MOTIVAZIONINON SEMPRE UN AUTOMA DETERMINISTICO E’ SUFFICIENTEMENTE FLESSIBILE PER MODELLIZARE LA REALTA’:
1. PUO’ ACCADERE DI NON CONOSCERE CON ESATTEZZA LO STATO INIZIALE;
2. NON SEMPRE E’ CONOSCIUTO L’EFFETTO ESATTO DI UN EVENTO (LO STESSO
EVENTO PUO’ CAUSARE TRANSIZIONI VERSO PIU’ STATI);
3. POSSONO ACCADERE TRANSIZIONI SENZA CHE ALCUN EVENTO VENGA
OSSERVATO ( -TRANSIZIONI).
NONDETERMINISTIC AUTOMATA(GENERALIZZAZIONE DEL CONCETTO DI AUTOMA DETERMINISTICO)
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
NONDETERMINISTIC AUTOMATADef. (Automa non deterministico): UN AUTOMA NON DETERMINISTICO, DENOTATO CON Gnd, E’ UNA SESTUPLA:
DOVE:
1. E’ L’INSIEME DEGLI STATI ASSOCIATI A Gnd;
2. E’ L’INSIEME DEGLI EVENTI ASSOCIATI A Gnd;
3. E’ LA FUNZIONE DI TRANSIZIONE (FUNZIONE
PARZIALE);
4. FUNZIONE EVENTI POSSIBILI:
;
5. INSIEME DI POSSIBILI STATI INIZIALI;
6. INSIEME DI STATI MARCATI.
),,,,,( 0 mndnd XxfEXG
X
E
Xnd EXf 2:
EX 2:
Xx 0XXm
}),(:{)( definitoexfEex nd
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
NONDETERMINISTIC AUTOMATA (cont.: esempio)
transitionfnd 2),0(
0
1
2
a
b
b
b definitanonbfnd ),0(
)(}2,1{),1( insiemebfnd
Come per gli automi deterministici,
vogliamo estendere la funzione
su
ndf
*E reachInsieme
},{ baE
}3,2,1{X
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
INSIEME -REACH(X)
)(:),()(, xRxeconvenzionPerxfxRXx
NELL’ ESTENDERE fnd OCCORRE CONSIDERARE IL RUOLO DELLE :itransizion
Def. ( -reach(x) ):
INSIEME DEGLI STATI RAGGIUNGIBILI DA x SEGUENDO LE TRANSIZIONI NEL
DIAGRAMMA DEGLI STATI CHE SONO ETICHETTATE CON .
xaassociatoincertezzadiinsiemexR "")(
)()(, xRURXUUx
Def. ( -reach(U) ):
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
FUNZIONE DI TRANSIZIONE ESTESA
estndfDef. (Funzione di transizione estesa ):
L’OPERAZIONE DI CONSENTE DI CONSIDERARE, AD OGNI PASSO,
L’EFFETTO DELLE
reach
DEFINIZIONE RICORSIVA:
)(),( xRxf estnd
)}),(),,(:({),( sxfyeyftXtRsexf estndnd
estnd
itransizion
reach reach reach reach0x
1e 2e 3e
...
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
LINGUAGGIO GENERATO E LINGUAGGIO MARCATO
Def. (Linguaggio generato da automa non deterministico):
}),(:{)( ,0* definitosxfxxEsGL est
ndnd
Def. (Linguaggio marcato da automa non deterministico):
}),(:)({)( ,0 OXsxfxxGLsGL mestndndndm
INTERPRETAZIONE: UNA STRINGA E’ NEL LINGUAGGIO GENERATO DA Gnd SE ESISTE UN PERCORSO CHE PARTE DALL’INSIEME x0 ED E’ ETICHETTATO DA
QUELLA STRINGA.
INTERPRETAZIONE: UNA STRINGA E’ NEL LINGUAGGIO MARCATO SE “E’ POSSIBILE CHE CONDUCA” AD UNO STATO MARCATO.
Facoltà di Ingegneria
Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:
INGEGNERIAAUTOMAZIONE II2LINGUAGGI FORMALI ED AUTOMIPROF. ALESSANDRO DE CARLIDR. VINCENZO SURACI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIS) 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), Paragrafo. 2.2 (The Concepts of Languages and Automata) ;
BIBLIOGRAFIA DELLA LEZIONE
[2] A. Di Febbraro, A. Giua, Sistemi ad Eventi Discreti, Mc-Graw-Hill Editore. Capitolo 2 (Sistemi ad Eventi Discreti Logici), fino al Paragrafo 2.4.2 (Automi come Riconoscitori di Sequenze).