Appunti Automazione digitale per la produzione sostenibile

CHIUSURA DI KLEENE (L*= ε U L U LL U LLL U …)

Il linguaggio L* contiene tutte le possibili concatenazioni di qualsiasi numero di stringhe appartenenti a L inclusa la stringa vuota.

POST LINGUAGGIO (L=L/s)

L/s contiene tutte le stringhe che si possono ottenere concatenando qualsiasi stringa in L con qualsiasi suffisso.

PROIEZIONE

Operazione che permette di prendere solo una parte di un insieme di eventi ed ignorare gli altri.

PROIEZIONE INVERSA

È una funzione che prende una stringa di un sottoinsieme di E e restituisce l'insieme di tutte le stringhe di E che si proiettano sulla stringa data.

AUTOMA

Un automa è una sestupla G= (X, E, f, Γ, x₀, Xm) dove:

1. Insieme di stati (nodi): X
2. Insieme degli eventi (archi): E
3. Funzione di transizione: f
4. Insieme degli eventi attivi: Γ
5. Stato iniziale: x₀
6. Insieme di stati finali (marcati): Xm

Un automa può essere:

DETERMINISTICO

Un automa è deterministico se dato uno...

stato in input non esistono 2 transizioni con lo stesso evento in uscita che portano a 2 stati differenti. NON DETERMINISTICO

Un automa è non deterministico se dato uno stato in input esistono più transizioni con lo stesso evento in uscita che portano a più stati differenti. In questo caso si possono avere più stati iniziali e in generale all'insieme degli eventi viene aggiunto l'evento nullo ε.

AUTOMI EQUIVALENTI

Due automi sono equivalenti se marcano e generano lo stesso linguaggio.

AUTOMA BLOCCANTE (deadlock)

Un automa è bloccante se presenta situazioni di (arrivo in uno stato non marcato in cui non ci sono archi uscenti) e/o (arrivo in più stati non marcati in cui non ci sono archi uscenti).

MACCHINA DI MOORE

È un automa dove lo stato corrente rappresenta anche le uscite.

MACCHINA DI MELAY

È un automa dove l'evento è rappresentato tramite la forma ingresso e uscita.

OPERAZIONI SUGLI...

AUTOMIPARTE ACCESSIBILE

• È un automa che rappresenta tu� gli sta� raggiungibili a par�re da x0

PARTE COACCESSIBILE

• È un automa che rappresenta tu� gli sta� tali per cui esiste un percorso che termina in Xm

TRIM

• È un automa cos�tuito dagli sta� appartenen� alla parte coaccessibile della parte accessibile oviceversa.

PROIEZIONE

• Consiste nel cos�tuire tu� gli even� dell’insieme E ecceto di quello del insieme più piccolo Es conl’evento vuoto ε. (quindi non deterministico)

PROIEZIONE INVERSA

• Si inserisce in ogni stato dell’automa un auto loop per tu� gli even� in El\Es (Es è un sotoinsiemedi El)

COMPLEMENTO

• Step 1: inserisco stato xd chiamato DEAD STATE (stato morto)
• Step 2: Marco gli sta� non marca� e smarco gli sta� marca�.

PRODOTTO

• Il prodoto tra due automi res�tuisce un automa che rappresenta tute le possibili combinazioni deidue automi di partenza.

Le transizioni del prodotto avvengono in modo sincronizzato, il che implica che entrambi gli automi devono eseguire una transizione contemporaneamente per passare a un nuovo stato.

COMPOSIZIONE PARALLELA

• La composizione tra due automi restituisce un automa che rappresenta tutte le possibili combinazioni, ma le interazioni avvengono indipendentemente l'una dall'altra.

AFFINAMENTO DELLO SPAZIO DI STATO

L'affinamento serve per confrontare due linguaggi, cioè comparare gli insiemi degli eventi attivi nei due automi. Questo viene fatto tramite il prodotto tra i due automi ed il risultato viene chiamato G = G1xG2.

NUOVO SUBAUTOMA

Un subautoma G1 è indicato come:

Q1 = Q1 x Q2

I1 = I1 x I2

T1 = T1 x T2

Q1' = Q1 x Q2

I1' = I1 x I2

T1' = T1 x T2

Per costruire un subautoma bisogna modificare i due automi G1 e G2 seguendo la procedura:

1. Costruire G1' = G1 x G2
2. Esaminare gli stati x1 di G1 ed aggiungere un autoloop per ogni evento in E2\ Γ(x1) e chiamare il risultato G1sl
3. Costruire G2' = G1

xG2slOSSERVATOREL'osservatore è un automa deterministico che viene costruito partendo da un automa non deterministico al fine di ottenere un automa equivalente ma in modo deterministico. Si può costruire come segue:MINIMAZIONE SPAZIO A STATOServe per trovare stati ridondanti/equivalenti e accorparli per trovare l'automa che marca il linguaggio K e che ha cardinalità minima. Due stati sono equivalenti se il loro comportamento futuro in termini di linguaggio marcato è lo stesso.OSSERVATORE CON EVENTI NON OSSERVABILI (des parzialmente osservabili)Gli eventi non osservabili possono essere considerati come l'evento ε degli automi non deterministici.MODELLAZIONE NON DETERMINISTICADue eventi non osservabili possono essere usati per modellare forme di non determinismo.DIAGNOSI DEGLI EVENTISignifica cercare di sapere se un evento non osservabile può essere accaduto o dev'essere accaduto. Verificare ciò siUtilizza l'OSSERVATORE DIAGNOSTICO. Questo può diagnosticare un singolo evento non osservabile alla volta. Si realizza come l'osservatore classico ma aggiungo un'etichetta ad ogni stato: Y agli stati che possono essere raggiunti da Xo tramite stringhe inosservabili che contengono almeno una volta ed X altrimenti. Se lo stato z può essere raggiunto sia con che senza eseguire ed allora creo due stati Zn e Zy. DIAGNOSTICABILITÀ Un evento ed non è diagnosticabile se in un linguaggio vivo (no deadlock o livelock) ci sono due stringhe sn e sy tali che: