Facoltà di Ingegneria Corso di Laurea: Insegnamento: Lezione n°: Titolo: Docenti: INGEGNERIA...

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

mailto:[email protected]






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






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






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






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






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






OPERAZIONI SUI LINGUAGGIConcatenazione di due linguaggi:

Prefix-clousure:

Kleene-clousure:

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

DEFDEF

},:{ *** LstEtEsLELDEF

LLLLLLLLLLLELDEF

}{**

….

Substring-clousure;

Suffix-clousure ;






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)






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






MODELLI AD EVENTI DISCRETI: AUTOMATA

(RAPPRESENTARE/GENERARE I LINGUAGGI)






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






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






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






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.






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






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;






EQUIVALENZA (PER LINGUAGGI) TRA AUTOMI

Def. (Equivalenza per linguaggio): DUE AUTOMI G E G’ SONO EQUIVALENTI (PER

LINGUAGGIO) SE:

)'()()'()( GLGLGLGL mm

ESEMPIO






BLOCKING: DEADLOCKS AND LIVELOCKS






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






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






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.






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






AUTOMI NON DETERMINISTICI






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)






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






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






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






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

...






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.






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


Facoltà di Ingegneria Corso di Laurea: Insegnamento: Lezione n°: Titolo: Docenti: INGEGNERIA...

Documents

Transcript of Facoltà di Ingegneria Corso di Laurea: Insegnamento: Lezione n°: Titolo: Docenti: INGEGNERIA...