vuoi
o PayPal
tutte le volte che vuoi
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:
- Insieme di stati (nodi): X
- Insieme degli eventi (archi): E
- Funzione di transizione: f
- Insieme degli eventi attivi: Γ
- Stato iniziale: x₀
- 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
- È un automa che rappresenta tu� gli sta� tali per cui esiste un percorso che termina in Xm
- È un automa cos�tuito dagli sta� appartenen� alla parte coaccessibile della parte accessibile oviceversa.
- Consiste nel cos�tuire tu� gli even� dell’insieme E ecceto di quello del insieme più piccolo Es conl’evento vuoto ε. (quindi non deterministico)
- Si inserisce in ogni stato dell’automa un auto loop per tu� gli even� in El\Es (Es è un sotoinsiemedi El)
- Step 1: inserisco stato xd chiamato DEAD STATE (stato morto)
- Step 2: Marco gli sta� non marca� e smarco gli sta� marca�.
- 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:
- Costruire G1' = G1 x G2
- Esaminare gli stati x1 di G1 ed aggiungere un autoloop per ogni evento in E2\ Γ(x1) e chiamare il risultato G1sl
- Costruire G2' = G1