DISCRETE EVENT SYSTEMS

27
Facoltà di Ingegneria Corso di Laurea: Insegnamento: Lezione n°: Titolo: Docenti: INGEGNERIA AUTOMAZIONE I 2 LINGUAGGI FORMALI ED AUTOMI DR. 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 LINGUAGGI FORMALI ED AUTOMI Redazione a cura del Dr. Ing. Francesco Liberati ([email protected]

description

DISCRETE EVENT SYSTEMS. LINGUAGGI FORMALI ED AUTOMI. Redazione a cura del Dr. Ing. Francesco Liberati ( [email protected] ). INDICE DELLA LEZIONE. INTRODUZIONE AI LINGUAGGI FORMALI . LINGUAGGI FORMALI ALFABETO, PAROLE, LINGUAGGI; OPERAZIONI SUI LINGUAGGI. AUTOMI - PowerPoint PPT Presentation

Transcript of DISCRETE EVENT SYSTEMS

Page 1: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

LINGUAGGI FORMALI ED AUTOMI

Redazione a cura del Dr. Ing. Francesco Liberati ([email protected])

Page 2: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

INTRODUZIONE AI LINGUAGGI FORMALI.

LINGUAGGI FORMALI

ALFABETO, PAROLE, LINGUAGGI;

OPERAZIONI SUI LINGUAGGI.

AUTOMI

LINGUAGGI GENERATI E MARCATI;

EQUIVALENZA TRA AUTOMI;

BLOCKING.

BIBLIOGRAFIA

Page 3: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

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

Page 4: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

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 ':||

Page 5: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

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

Page 6: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

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

Page 7: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

OPERAZIONI SUI LINGUAGGIConcatenazione di due linguaggi:

Prefix-clousure:

Kleene-clousure:

},,:{),(, **BABABABA LbLaabsEsLLLLconcELL

DEFDEF

},:{ *** LstEtEsLELDEF

LLLLLLLLLLLELDEF

}{**

Page 8: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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 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)

Page 9: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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 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

Page 10: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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 AD EVENTI DISCRETI: AUTOMATA

(RAPPRESENTARE/GENERARE I LINGUAGGI)

Page 11: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

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

Page 12: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

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

Page 13: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

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).

Page 14: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

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.

Page 15: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

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

Page 16: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

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;

Page 17: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

BLOCKING: DEADLOCKS AND LIVELOCKS

Page 18: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

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

Page 19: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

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

Page 20: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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 NON DETERMINISTICI

Page 21: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

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).

AUTOMI NON DETERMINISTICI(GENERALIZZAZIONE DEL CONCETTO DI AUTOMA DETERMINISTICO)

Page 22: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

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

Page 23: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

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

Page 24: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

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) ):

Page 25: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

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

...

Page 26: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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

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.

Page 27: DISCRETE EVENT SYSTEMS

Facoltà di Ingegneria

Corso di Laurea:Insegnamento:Lezione n°:Titolo:Docenti:

INGEGNERIAAUTOMAZIONE I2LINGUAGGI FORMALI ED AUTOMIDR. 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), Paragrafo. 2.2 (The Concepts of Languages and Automata) ;

PER APPROFONDIRE

[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).