Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
DISCRETE EVENT SYSTEMS
LINGUAGGI FORMALI ED AUTOMI
Redazione a cura del Dr. Ing. Francesco Liberati ([email protected])
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
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
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
INTRODUZIONE
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).
DES
INSIEME DI POSSIBILI
SEQUENZE DI EVENTI
(LINGUAGGI)
CVDS
MODELLI DIFFERENZIALI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
PAROLA
PRESO 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:
E  {a, b, c} Parole :  , abc, bacba,...
 stringa vuota (definita su ogni alfabeto)
LA LUNGHEZZA DI UNA PAROLA È DATA DAL NUMERO DI LETTERE (EVENTI) CONTENUTE
NELLA PAROLA.
| s |:
lunghezza stringa s (|  | 0
| s |e :
frequenza dell ' evento e nella stringa s
per convenzione)
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
PRIME OPERAZIONI FONDAMENTALI
Chiusura 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 s  E DENOTIAMO UNA GENERICA PAROLA GENERATA DA E.
Concatenazione di due Parole:
conc : E *  E *  E * s, t  E * , conc( s, t )  st ,
DOVE st È LA STRINGA COSTITUITA DAGLI EVENTI IN s IMMEDIATAMENTE SEGUITI
DAGLI EVENTI IN t.
s  s1s2 s3 , con s1 , s2 , s3  E *
PREFISSO
SOTTOSTRINGA
SUFFISSO
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
LINGUAGGIO
PRESO 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:
L  E*.
 linguaggio vuoto
COME DEFINIRE UN LINGUAGGIO:
1. DEFINIZIONE ENUMERATIVA (SI ELENCANO TUTTE LE PAROLE CONTENUTE NEL
LINGUAGGIO). POSSIBILE PER LINGUAGGI FINITI. ES:
E  {a, b, c} L1  { , a, b, c, aa, abc}
2. DEFINIZIONE VERBALE/INSIEMISTICA:
L  {s  E * :| s | 2} L  {tutte le stringhe di lunghezza finita che finiscono per b}
3. AUTOMI E MODELLI.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
OPERAZIONI SUI LINGUAGGI
Concatenazione di due linguaggi:
LA , LB  E
DEF
DEF
conc( LA , LB )  LA LB  {s  E * : s  ab, a  LA , b  LB }
*
Prefix-clousure:
LE
*
DEF
L  {s  E * : t  E * , st  L}
Kleene-clousure:
LE
*
DEF
L  { }  L  LL  LLL  LLLL  
*
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
OPERATORI DI PROIEZIONE NATURALE
Proiezione di stringhe:
P:E  E
*
P
P ( )  
*
A
P (e) 
e if e  EA
P( se)  P( s) P(e)
for s  EP* , e  EP
 if e  EP \ EA
PROIEZIONE
EVENTO NULLO
PROIEZIONE
STRINGA
PROIEZIONE
EVENTO
*
LA PROIEZIONE DA UN INSIEME DI EVENTI DI PARTENZA E P AD UN INSIEME DI EVENTI
DI ARRIVO
IN
E A*
E A ).
E A* , ASSOCIA AD UNA GENERICA PAROLA
IN
E P*
LA PAROLA PIU’ “SIMILE”
(OTTENUTA CANCELLANDO DALLA PAROLA GLI EVENTI NON CONTENEUTI IN
.
1
P :E 2
*
A
EP*
P1 (t )  {s  EP* : P(s)  t}
(Proiezione inversa)
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
OPERATORI DI PROIEZIONE NATURALE (cont.)
Proiezione di linguaggi:
L  EP*
P( L)  {s  E A* : t  L, P(t )  s}
LA PROIEZIONE DI UN LINGUAGGIO SI OTTIENE SEMPLICEMENTE PROIETTANDO LE
PAROLE CONTENUTE NEL LINGUAGGIO.
Alcune proprietà delle proiezioni:
P( P 1 ( L))  L L  P 1 ( P( L))
P( A  B)  P( A)  P( B) P( A  B)  P( A)  P( B)
P 1 ( A  B)  P 1 ( A)  P 1 ( B) P 1 ( A  B)  P 1 ( A)  P 1 ( B)
P( AB)  P( A) P( B) P 1 ( AB)  P 1 ( A) P 1 ( B)
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
MODELLI AD EVENTI DISCRETI:
AUTOMATA
(RAPPRESENTARE/GENERARE I LINGUAGGI)
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
AUTOMATA
COME 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):
X  {x, y, z}
OSSERVAZIONI:
E  {a, b, c}
STATO INIZIALE
1.
STATO MARCATO
2.
E  {a, b, c}
f ( y, a )  y ;
3.
f ( x, a )  f ( x, b )  y ;
4.
f. funzione parziale (PER UN DATO
a,b
x
y
a
a
z
b
Funzione di transizion e :
f : X E  X
Es :
f ( x, a )  y f ( z , a )  x
c EVENTO NON ATTIVO;
STATO, NON TUTTI I VALORI DELLA
FUNZIONE f SUL PRODOTTO X x E SONO
DEFINITI. AD ESEMPIO, f(z,b) NON E’
DEFINITO).
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
AUTOMATA (cont.)
Def. (Automa): UN AUTOMA DETERMINISTICO, DENOTATO CON G, E’ UNA SESTUPLA:
G  ( X , E, f , , x 0 , X m )
DOVE:
1.
X
E’ L’INSIEME DEGLI STATI ASSOCIATI A G;
2.
E
E’ L’INSIEME DEGLI EVENTI ASSOCIATI A G;
3.
f : X E  X
4.
 : X  2E
5.
x0
6.
Xm  X
E’ LA FUNZIONE DI TRANSIZIONE (FUNZIONE PARZIALE);
FUNZIONE EVENTI POSSIBILI:
( x)  {e  E : f ( x, e) definito};
STATO INIZIALE;
INSIEME DI STATI MARCATI.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
AUTOMATA (cont.: OSSERVAZIONI)
IN COMPUTER SCIENCE LA FUNZIONE
DEFINITA SUL PRODOTTO X  E .
f : X E  X
E’ IN GENERE COMPLETAMENTE
L’AUTOMA E’ DETERMINISTICO POICHE’ LA FUNZIONE DI TRANSIZIONE E’ MONODROMA
(AD UN PUNTO DELLO SPAZIO DI PARTENZA ASSOCIA UN SOLO PUNTO DELLO SPAZIO
X
DI ARRIVO). NEGLI AUTOMI NON DETERMINISTICI SI HA f : X  E  2 .
DATO UN INSIEME S, L’INSIEME
DI TUTTI I SOTTOINSIEMI DI S .
2,S DETTO INSIEME POTENZA DI S , DENOTA L’INSIEME
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).
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
AUTOMATA E LINGUAGGI
E’ UTILE ESTENDERE LA FUNZIONE DI TRANSIZIONE DALL’INSIEME
X E
ALL’INSIEME
X  E *.
Funzione di transizione estesa:
f : X  E*  X
f ( x,  )  x
f ( x, se)  f ( f ( x, s), e) e  E , s  E *
PARTENDO DA QUESTA GENERALIZZAZIONE DELLA FUNZIONE DI TRANSIZIONE, E’
IMMEDIATO CAPIRE COME, ED IN CHE SENSO, GLI AUTOMATA GENERANO LINGUAGGI.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
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:
L(G )  {s  E * : f ( x0 , s) definito}
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:
{ f ( x0 , s) definito}  { f ( f ( x0 , p), e) definito, s  pe}
2.
SE f E’ UNA FUNZIONE TOTALE, ALLORA
L(G)  E *.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
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:
Lm (G )  {s  E * : f ( x0 , s)  X m }
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;
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
BLOCKING: DEADLOCKS AND LIVELOCKS
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
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:
Deadlock:
Livelock:
S  X \ X m fortemente connesso :
x  X \ X m : ( x)  
{x  S f ( x, e)  S e  ( x)}
x
s1
s2
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
BLOCCO (cont.: interpretazione)
SI HA IN GENERALE:
Lm (G )  Lm (G )  L(G )
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:
Lm (G )  L(G )
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
AUTOMI NON DETERMINISTICI
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
MOTIVAZIONI
NON 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)
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
NONDETERMINISTIC AUTOMATA
Def. (Automa non deterministico): UN AUTOMA NON DETERMINISTICO, DENOTATO CON
Gnd, E’ UNA SESTUPLA:
Gnd  ( X , E   , f nd , , x 0 , X m )
DOVE:
1.
X
E’ L’INSIEME DEGLI STATI ASSOCIATI A Gnd;
2.
E
E’ L’INSIEME DEGLI EVENTI ASSOCIATI A Gnd;
3.
f nd : X  E    2 X
4.
 : X  2E
5.
x0  X
INSIEME DI POSSIBILI STATI INIZIALI;
6.
Xm  X
INSIEME DI STATI MARCATI.
E’ LA FUNZIONE DI TRANSIZIONE (FUNZIONE PARZIALE);
FUNZIONE EVENTI POSSIBILI:
( x)  {e  E : f nd ( x, e) definito};
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
NONDETERMINISTIC AUTOMATA (cont.: esempio)

f nd (0,  )  2
b
0
a
E  {a, b}
X  {1,2,3}
f nd (0, b)
2
  transition
non definita
f nd (1, b)  {1,2}
b
1
b
(insieme )
Come per gli automi deterministici,
vogliamo estendere la funzione f nd
*
su E
Insieme   reach
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INSIEME
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
 -REACH(X)
NELL’ ESTENDERE fnd OCCORRE CONSIDERARE IL RUOLO DELLE

Def. ( -reach(x) ):
  transizion i :
x  X , R( x)  f ( x,  ) Per convenzione : x  R( x)
INSIEME DEGLI STATI RAGGIUNGIBILI DA x SEGUENDO LE TRANSIZIONI NEL
DIAGRAMMA DEGLI STATI CHE SONO ETICHETTATE CON
.
R( x) insieme " di incertezza" associato a x

Def. ( -reach(U) ):
U  X , R(U )   R( x)
xU
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
FUNZIONE DI TRANSIZIONE ESTESA
DEFINIZIONE RICORSIVA:
Def. (Funzione di transizione estesa
f ndest ):
f ndest ( x,  )  R( x)
f ndest ( x, se)  R({t  X : t  f nd ( y, e), y  f ndest ( x, s )})
L’OPERAZIONE DI 
DELLE
 reach
  transizion i
CONSENTE DI CONSIDERARE, AD OGNI PASSO, L’EFFETTO
x0
  reach
e3
e2
e1
  reach
  reach
  reach
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
...
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
LINGUAGGIO GENERATO E LINGUAGGIO MARCATO
Def. (Linguaggio generato da automa non deterministico):
L(Gnd )  {s  E* : x  x0, f ndest ( x, s) definito}
INTERPRETAZIONE: UNA STRINGA E’ NEL LINGUAGGIO GENERATO DA Gnd SE ESISTE UN
PERCORSO CHE PARTE DALL’INSIEME x0 ED E’ ETICHETTATO DA QUELLA STRINGA.
Def. (Linguaggio marcato da automa non deterministico):
Lm (Gnd )  {s  L(Gnd ) : x  x0, f ndest ( x, s)  X m  O}
INTERPRETAZIONE: UNA STRINGA E’ NEL LINGUAGGIO MARCATO SE “E’ POSSIBILE
CHE CONDUCA” AD UNO STATO MARCATO.
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it
Corso di Laurea:
Insegnamento:
Lezione n°:
Titolo:
Docenti:
INGEGNERIA
AUTOMAZIONE I
2
LINGUAGGI FORMALI ED AUTOMI
DR. VINCENZO SURACI
Facoltà di Ingegneria
PER APPROFONDIRE
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) ;
[2]
A. Di Febbraro, A. Giua, Sistemi ad Eventi Discreti, McGraw-Hill Editore. Capitolo 2 (Sistemi ad Eventi Discreti Logici), fino
al Paragrafo 2.4.2 (Automi come Riconoscitori di Sequenze).
SAPIENZA - Università di Roma – Dipartimento di Ingegneria Informatica Automatica e Gestionale Antonio Ruberti (DIIAG)
Via Ariosto 25 - 00185 Roma – http://www.dis.uniroma1.it