Automi

Materie:Appunti
Categoria:Sistemi
Download:185
Data:14.06.2007
Numero di pagine:3
Formato di file:.doc (Microsoft Word)
Download   Anteprima
automi_1.zip (Dimensione: 10.51 Kb)
trucheck.it_automi.doc     71.5 Kb
readme.txt     59 Bytes


Testo

Relazione di sistemi...
Definizione di automa
L’automa o macchina è definito come l’insieme delle I (variabili d’ingresso), VI (valori delle variabili d’ingresso), U (variabili d’uscita), VU (valore delle variabili d’uscita), S (stati) e T (tempi) e dalle rispettive funzioni f (transizione degli stati) e g (trasformazione delle uscite).
Automi di Moore e Mealy
L’automa di Moore descrive la funzione f (s(t2)=f(t2,t1,s(t1),VI n(t1))) e la funzione g (VU r(t2)=g(t2,t1,s(t1))), dove la funzione f ha dei VI e la funzione g ha come ingressi le uscite di f, invece Mealy era d’accordo con la funzione f di Moore ma nella funzione g affermava che g aveva in ingresso le uscite della funzione f, ma aveva anche propri ingressi (VU r(t2)=g(t2,t1,s(t1),VI n(t1))).Gli automi vengono rappresenta ti tramite il diagramma degli stati.

Secondo Moore Secondo Mealy
Proprietà fondamentali degli automi
Le proprietà fondamentali degli automi sono:
lo stato iniziale, dove la macchina si trova all’inizio del suo funzionamento;
lo stato finale, dove la macchina non può più muoversi per qualsiasi VI;
lo stato di equilibrio, dove la macchina può rimanere per un VI in un tempo indefinito;
l’uscita di equilibrio,che è l’uscita comune a tutti gli stati.
Un automa si dice reversibile quando dati un i e uno stato s2 ci si uno stato s1 che possa arrivare allo stato s2 grazie all’ingresso i e invertendo l’ordine delle frecce del diagramma degli stati si ottiene ancora un diagramma degli stati.
Un automa si dice raggiungibile quando è presente una sequenza di VI che facciano passare lo stato s1 allo stato s2.
La minimizzazione di un automa
La minimizzazione in pratica è il procedimento che riduce l’automa su cui stiamo lavorando. Per parlare di minimizzazione dobbiamo innanzitutto dire che due stati si dicono indistinguibili se a ingressi uguali corrispondono uscite e stato d’arrivo, mentre si dicono distinguibili se a ingressi uguali non corrispondono le uscite e gli stati d’arrivo. Per svolgere una minimizzazione partiamo da una tabella iniziale (tabella da minimizzare) a due ingressi, da una parte gli stati e dall’altra i VI. Dopo creiamo la tabella di equivalenza formata dagli stati della tabella iniziale, andiamo a confrontare tutte le uscite delle VI se sono distinguibili allora li segneremo con un segno X, se sono indistinguibili lasceremo lo spazio vuoto. Faremo dopo la stessa cosa con gli ingressi delle VI se sono distinguibili allora faremo un cerchio, se sono indistinguibili non faremo nulla. Successivamente andremo a formare i cicli, guardando nella tabella di equivalenza gli spazi rimasti vuoti, e dopo andremo a eleggere i rappresentanti dei cicli che andranno a formare la tabella finale. Infine la tabella viene rappresentata tramite diagramma degli stati, formato dai cerchi che contengono gli stati e dalle frecce che contengono gli ingressi e le uscite.
VI
S

1

0/0
1/0
1
2/0
3/1
2
4/0
5/0
3
6/0
7/0
4
0/0
1/0
5
2/0
3/1
6
4/0
5/0
7
6/0
7/0
Esercitazione

1
2
3
4
5
6
7

X0

X0

1
X0
X0
X
X0
X0
X
2
X0

X0

3

X

X

4
X0

X0

5
X0
X0
X
X0
X0
X
6
X0

X0

7

X

X

Tabella da minimizzare Tabella di equivalenza

Tabella finale
VI
S

1

0/0
1/0
1
0/0
3/1
3
0/0
3/0
Cicli
C0(S0,S2,S4,S6)=S0
C1(S1,S5)=S1
C2(S0,S2.S4,S6)=S0
C3(S3,S7)=S3
C4(S0,S2,S4,S6)=S0
C5(S1,S5)=S1
C6(S0,S2,S4,S6)=S0
C7(S3,S7)=S3
S(S0,S1,S3)
0/0
1/0
0/0
1/1
0/0
1/0
Esercitazione 2
Variabili d’ingresso = Plus T, Plus 1, Plus 2
Valori variabili d’ingresso = T, 1, 2
Variabili d’uscita = vai su, vai giù, stop
Valori variabili d’uscita = su, giù, stop
Stati = piano T, piano 1, piano 2
VI
S
T
1
2
PT
Stop
Su
Su
P1
Giù
Stop
Su
P2
Giù
Giù
Stop
T/Stop

P1/SU
T/Giù
P2/su T/Giù
P1/Giù
P2/Stop
P1/Stop
P2/SU

Esempio