+ All Categories
Home > Documents > AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p...

AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p...

Date post: 14-Mar-2020
Category:
Upload: others
View: 0 times
Download: 0 times
Share this document with a friend
19
CIAMPANI VIRGILIO AUTOMI A STATI FINITI Frosinone 2003
Transcript
Page 1: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

CIAMPANI VIRGILIO

AUTOMI A STATI FINITI Frosinone 2003

Page 2: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

AUTOMI A STATI FINITI ____________________________________________________________________________2

© Virgilio AUTOMI_A_STATI_FINITI

INTRODUZIONE

Normalmente il termine automa è associato all'altro ancor più generale di macchina indica un congegno che "imita i movimenti e le funzioni di un corpo animato". La parola automa deriva infatti dal greco autòmaton, meccanismo semovente e dal latino automâtus, che si muove da sé. In sostanza il concetto di automa è quello di una macchina capace di svolgere in maniera automatica, se sollecitata in modo opportuno [con segnali di ingresso], delle operazioni particolari più o meno complesse che portano a un preciso risultato.

L’AUTOMA INTRODUCE IL CONCETTO DI STATO Come si vede l'automa non è altro che un particolare sistema e per esso possono essere usate tutte le rappresentazioni simboliche e formali definite per i sistemi.

In particolare si ha a che fare con sistema che riceve in ingresso delle sollecitazioni rappresentate con dei classici segnali di ingresso e risponde in uscita con dei normali segnali d’uscita .

Fin qui niente di nuovo, ma allora cos’è che caratterizza un sistema in termini di comportamento al punto tale da farlo definire Automa ?. CHIARIAMOCI LE IDEE CON UN ESEMPIO: Supponiamo di avere un sistema in grado di contare il numero di merendine confezionato da una macchina imbustatrice. Ci sarà un nastro trasportatore dove le merendine appena confezionate passeranno per raggiungere un contenitore . Le merendine durante il percorso attraverseranno un punto in cui una fotocellula rileverà il loro passaggio generando un impulso elettrico [si veda fig. b] . FIG. b Questo impulso elettrico sarà il segnale di input per il sistema di conteggio delle merendine, il quale una volta raggiunto un valore prestabilito, emetterà un segnale di fine confezionamento a cui farà seguito

$ 34

la sostituzione del contenitore pieno con uno vuoto. Focalizziamo l’attenzione sul sistema di conteggio questo riceverà in ingresso segnali sempre identici (l’impulso di fig. b) e risponderà in modo diverso solo quando arriverà l’impulso associato all’ultima merendina di un contenitore. Questo significa che il sistema tiene a mente il numero di merendine che sono già passate. Il sistema è dotato di memoria ! Questa sua capacità di ricordare la propria storia passata viene espressa con il concetto di stato. Lo stato viene anche detto stato interno Lo stato abilita l’automa a rispondere in maniera diversa a identiche sollecitazioni in ingresso Il comportamento di un automa dipende, attraverso lo stato dalla sua storia passata E allora ? Tutte le volte che un sistema ha un modo di comportarsi come quello sopra descritto possiamo sicuramente affermare che il sistema è dotato di stato interno, ma questo non è purtroppo sufficiente per farci dire che siamo in presenza di un automa. Sono molti i sistemi dotati di memoria che non lo sono si pensi ai sistemi idraulici con serbatoio di accumulo e agli analoghi circuiti elettrici con i condensatori dove i due componenti serbatoio e condensatore fungono da elementi di memoria Quindi occorreranno altre prerogative per poter classificare un sistema come automa a stati finiti,

Page 3: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

AUTOMI A STATI FINITI ____________________________________________________________________________3

© Virgilio AUTOMI_A_STATI_FINITI

Quali caratteristiche deve avere un sistema per essere classificato come automa a stati finiti? “DINAMICO”

Deve essere un sistema le cui grandezze rappresentative (Ingressi,Stato, Uscite ) mutano i loro valori nel tempo

“DISCRETO” I valori assunti dalle grandezze di cui sopra appartengono ad ‘insiemi finiti

composti da valori ammissibili Gli ingressi agiscono sul sistema in istanti di tempo ben determinati Le uscite sono “osservabili” solo in determinati istanti di tempo Il passaggio tra uno stato e l’altro [Transizione di stato ] avviene in particolari

istanti di tempo

“DETERMINISTICO” A determinate sequenze di simboli di ingresso risponde sempre con

determinate sequenze di simboli d’uscita Perché si parla di sistemi Sequenziali ? Dal punto di vista ingresso- uscita come siamo abituati ad osservare i sistemi, l’automa riceve in ingresso una sequenza di simboli che rappresentano i valori che le grandezze di ingresso assumono e restituiscono in uscita una corrispondente sequenza di simboli appartenenti all’insieme dei valori assumibili dalle grandezze di Output.[SISTEMI SEQUENZIALI] Lo stato corrente del sistema riassume l'informazione circa la sequenza di ingresso fornita in passato e serve per determinare il comportamento del sistema al successivo ingresso (stato futuro). In un certo istante il sistema può trovarsi in uno stato scelto tra un numero finito di stati possibili

DEFINIZIONE FORMALE DI AUTOMA A STATI FINITI La teoria degli automi (o teoria degli automi finiti o teoria delle macchine a stati finiti o teoria delle macchine sequenziali), è uno dei più importanti settori della teoria generale dei sistemi. Da essa traiamo la definizione seguente: Un automa a stati finiti [FSA, Finite State Automaton ] è un sistema discreto definito formalmente da una quintupla : < I,O,S, δ, ω >

dove(*

vedi appendice il concetto di prodotto cartesiano e di funzione):

I è l’insieme finito dei simboli di ingresso I = {i1 ,i2,i3,….ip } O è l’insieme finito dei simboli d’uscita O = {o1 ,o2,o3,….om } S è l’insieme finito degli stati, S = {s1 ,s2,s3,….sn } δ : I X S S è la funzione di transizione dello stato

ω : I X S O è la funzione d’uscita, Questa è la definizione secondo Mealy; [Macchina di Mealy] Come si vede l’automa viene ad essere definito da tre insiemi e due funzioni. Esiste una seconda formalizzazione dell’automa che differisce dalla prima solo per la funzione d’uscita: ω’: S O Questa è la definizione secondo Moore [Macchina di Moore]

Page 4: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

AUTOMI A STATI FINITI ____________________________________________________________________________4

© Virgilio AUTOMI_A_STATI_FINITI

COMMENTO: La differenza tra i due modelli consiste nella diversa formalizzazione della modalità con cui viene calcolata l’uscita:

• Mentre nella macchina di Mealy l’uscita è funzione sia del simbolo d’ingresso applicato che dello stato interno in cui si trova il sistema.

• In quella di Moore l’uscita è funzione solo dello stato interno. NB: I due modelli sono del tutto equivalenti infatti un sistema rappresentabile come automa secondo Mealy può essere rappresentato come macchina di Moore.Ovvero dato un automa rappresentato secondo Mealy è sempre possibile convertirlo in uno equivalente secondo Moore.

MODELLO [DESCRIZIONE] DI UN AUTOMA Per descrivere un automa e la sua corrispondente macchina si può far ricorso a diverse rappresentazioni noi ne prenderemo in considerazione due e cioè:

1. DIAGRAMMA DEGLI STATI o PALLOGRAMMA 2. TABELLA DI STATI/USCITE o TABELLA DI TRANSIZIONE

IL DIAGRAMMA DEGLI STATI Il diagramma degli stati è un grafo orientato caratterizzato da n nodi ( n=|S|) e p x n (p=|I|) rami orientati colleganti coppie di nodi.

MEALY MOORE

Ih

Sj/oySi/Op

Ih /ok

SJ SI

Se c’è una transizione dallo stato si allo stato sj ricevuto l’ingresso ih, allora esiste un arco orientato da si a sj. Nella rappresentazione secondo Mealy ogni nodo rappresenta uno stato ed ogni ramo ha un’etichetta che rappresenta una coppia ingresso/uscita.

δ(ih,si) =sj e ω(ih,si)= ok Nella macchina di Moore l’uscita l’andremo ad inserire direttamente nel nodo insieme allo stato e si avrà:

ω’(sj)= oy

Sf

NB:Il diagramma degli stati permette, per alcuni tipi di automi per cui ciò ha significato, di identificare anche lo stato iniziale e gli stati finali dell'automa: lo stato iniziale è rappresentato da un nodo con una freccia entrante, mentre gli stati finali sono individuati da un nodo con doppio circolo.

S0

Page 5: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

AUTOMI A STATI FINITI ____________________________________________________________________________5

© Virgilio AUTOMI_A_STATI_FINITI

TABELLE DI TRANSIZIONE Le tabelle di transizione sono delle matrici [Array] bidimensionali con un numero di righe pari al numero degli stati ed un numero di colonne pari al numero dei simboli d’ingresso. MEALY N RIGHE [N =|S| ] E P COLONNE [ P=|I| ] I S

i1 i2 .. Ih . ip

s1

s2

.

si sj/ok

.

.

sn L’elemento aih (quello che ritrova all’incrocio tra la riga Si e la colonna ih ) è formato dalla coppia δ(ih,si) =sj e ω(ih,si)= ok cioè lo stato successivo calcolato con la funzione δ a partire dall’ingresso ih e dallo Si e dall’uscita ok calcolata a partire dagli stessi valori con la funzione ω. NEL CASO DI MODELLO DI MOORE :

[N RIGHE [ N= |S| ] E P+1 COLONNE P =|I|] si aggiunge una colonna per l’uscita I S

i1 i2 .. Ih . ip O

s1 s2 . si sj ok . . sn Queste tabelle , oltre ad essere un modello alternativo al diagramma degli stati per la rappresentazione di un automa sono indispensabili per procedere alla sintesi del circuito elettronico che implementa l’automa. In questa fase sono spesso chiamate: Tavole o tabelle di flusso .

Page 6: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

AUTOMI A STATI FINITI ____________________________________________________________________________6

PRIMO ESEMPIO DI AUTOMA DESCRIZIONE DEL PROBLEMA: Vogliamo progettare la logica di funzionamento di una macchina distributrice di biglietti della metropolitana . Il costo del biglietto e di 1,2 euro e le monete che la macchina accetta sono solo quelle da 1€ e da 0.2 € . 1° PASSO:[ANALISI SPECIFICHE VERBALI E/O SCRITTE] Si analizzano attentamente le specifiche verbali che descrivono il progetto cercando di trarre quante più possibili informazioni utili per ul successivo passo della formalizzazione . Ingressi: Due soli tipi di monete due soli possibili segnali di ingresso. Uscite : per gestire l’immissione errata di monete per attivare l’emissione del biglietto per avvertire come procedere Stati : In questa fase siamo solo in grado di prevedere che l’automa avrà certamente uno stato iniziale ed altri stati che rappresenteranno le mutate condizioni in cui il sistema si verrà trovare. 2° PASSO FORMALIZZAZIONE] [

[

Procediamo ad una prima codifica: ingressi: 1 € MG 0.2 € MP I = {MG, MP, AM} |I|=3 altre monete AM L’insieme dei simboli d’ingresso ha una cardinalità pari a 3

Uscite: Inserisci ancora monete A [sequenza non terminata]

Inserimento errato R [restituisci moneta errata] O = { A, R ,E } Sequenza di inserimento corretta E [emetti biglietto] |O|=3 Stati: Stato iniziale S0 in cui l’automa pronto in attesa di monete

Ogni altro stato necessario a differenziare la condizione in cui si trova il sistema

S = {S0, ………}

3° PASSO SINTESI CON DIAGRAMMA DEGLI STATI] M: MEALYDallo stato iniziale ci sono tre possibili input: se si inserisce una MP il sistema si verrà trovare in una nuova condizione [quella in cui è stata inserita una moneta da 0.2 € ] questo causerà una transizione di stato verso lo stato S1. Nel caso in cui si inserisca una moneta da 1 € il sistema modifica la sua condizione che dovrà esser differenziata da quella precedente con introduzione di un ulteriore stato S2. Nei primi due casi il sistema avvertirà l’utente segnalando il non completamento dell’operazione con il simbolo d’uscita A. Se si inserisce una moneta non ammessa il sistema resterà nello stato iniziale restituendo la stessa.

© Virgilio AUTOMI_A_STATI_FINITI

Page 7: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

AUTOMI A STATI FINITI ____________________________________________________________________________7

© Virgilio AUTOMI_A_STATI_FINITI

NB : Per ogni stato ci dovranno essere tanti archi uscenti quanti sono i simboli di ingresso. Solo così siamo sicuri di aver esaminato tutti i casi possibili.

AM /

MG / MP /

S2S1

S0

Dobbiamo fare la stessa cosa per gli altri due stati:

AM / R

MP/ R

AM / R

S2S1

AM / R MP / E

MP / A MG / A

MG / R

S0

MG / E

Ora che abbiamo terminato possiamo dire affermare che S = {S0,S1,S2 }

Page 8: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

AUTOMI A STATI FINITI ____________________________________________________________________________8

© Virgilio AUTOMI_A_STATI_FINITI

Allo stesso risultato possiamo arrivare utilizzando le tabelle di transizione:

i s AM MG MP

S0 S0/R S2/A S1/A

S1 S0/R S0/E S1/R

S2 S0/R S2/R S0/E

Come si vede le stesse informazioni presenti nel diagramma degli stati sono in questa tabella: Rappresentano lo stesso sistema !.: NB Il passaggio dal diagramma degli stati alla tabella di transizione non è altro che una scrittura orientata alla sintesi . Andrà fatta ,sempre perché indispensabile alla realizzazione dei circuiti che implementano il sistema. M: MOORE Vediamo di progettare lo stesso automa utilizzando il modello di Moore:

Come si vede aumentano gli stati questo perché nella macchina di Moore occorre distinguere le uscite

Page 9: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

AUTOMI A STATI FINITI ____________________________________________________________________________9

© Virgilio AUTOMI_A_STATI_FINITI

Vediamo la corrispondente tabella di transizione

I S

MG MP AM O

S0 S1 S2 S3 - - S1 S4 S6 S4 A S2 S6 S5 S5 A S3 S1 S2 S3 R S4 S4 S6 S4 R S5 S6 S5 S5 R S6 S1 S2 S3 E

Le due macchine risultano essere del tutto equivalenti dal punto di vista ingresso-uscita: a sequenze d’ingresso uguali risponderanno con identiche sequenze d’uscita.

SECONDO ESEMPI DI AUTOMA [ASCENSORE] Progettare la logica di funzionamento di un sistema capace di controllare un ascensore per una palazzina di

tre piani.

ALL T12La pulsantiera prevede i seguenti comandi: Si cerchi di formalizzare il problema in modo da risolverlo con un automa a stati finiti.

1° PASSO [ANALISI SPECIFICHE SCRITTE E/O VERBALI] Dalle specifiche si può dedurre: Ingressi Saranno quattro quanti sono i pulsanti sulla pulsantiera dell’ascensore Stati Anche qui c’è poco da dire saranno tanti quanti sono i piani su cui può sostare l’ascensore Uscite Occorreranno delle uscite per comandare la salita o la discesa ai piani Occorrerà una segnalazione in caso di allarme. 2° PASSO [FORMALIZZAZIONE] Procediamo ad una prima codifica: ingressi: 1P Segnale inserito per salire al primo piano 2P Segnale inserito per salire al secondo piano T Segnale inserito per portarsi al primo terra ALL Segnale per gestire una situazione anomala Uscite: “Primo” vai al primo piano “Secondo” vai al secondo piano “Terra” vai al piano terra “SOS” Segnala condizione anomala Stati: S0 piano terra S1 primo piano S2 secondo piano

Page 10: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

AUTOMI A STATI FINITI ____________________________________________________________________________10

© Virgilio AUTOMI_A_STATI_FINITI

[3° PASSO SINTESI CON DIAGRAMMA DEGLI STATI] Cominciamo partendo dallo stato S0 a progettare l’automa per mezzo del diagramma degli stati:

S0 Nel caso in cui venga premuto il pulsante 1P e l’ascensore dovrà recarsi al primo piano con segnale d’uscita “Primo”.

S1

1P/”Primo”

S0 nel caso in cui venga premuto il pulsante 2P, si avrà un comportamento come quello indicato sotto

2P/”Secondo” 1P/”Primo”

S2 S1

S0 A questo punto, lasciando da parte per il momento il pulsante ALL, non ci resta che il pulsante T per completare la descrizione del comportamento ammissibile dallo stato S0; in questo caso, il comando richiesto sarà ininfluente e quindi l’ascensore non farà altro che rimanere al piano terra; Nella rappresentazione grafica, questo è indicato con un arco partirà dallo stato S0 e ritornerà sempre in S0 con segnale d’uscita “Terra”.

2P/”Secondo” 1P/”Primo”

S2 S1

S0

T/”Terra”

Page 11: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

AUTOMI A STATI FINITI ____________________________________________________________________________11

© Virgilio AUTOMI_A_STATI_FINITI

Terminata l’analisi relativa allo stato lo stato S0, possiamo completare il grafo procedendo allo stesso modo sia per S1 che per S2

T/”Terra”

T/”Terra”

S2 S1

S0

2P/”Secondo”1P/”Primo”

1P/”Primo”

2P/”Secondo” quindi:

1P/”Primo”

1P/”Primo”

1P/”Primo”

T/”TerraT/”Terra”

2P/”Secondo”

2P/”Secondo”

T/”Terra”

S2 S1

S0

2P/”Secondo” OSSERVAZIONE: ogni stato deve avere un numero di archi uscenti pari ai simboli d’ingresso dell’automa. A questo punto non ci resta che esaminare il comportamento del sistema in risposta al segnale di input ALL Attenzione, ogni ascensore si differenzia da altri per più motivi, il più comune è proprio questo: l’interpretazione del pulsante ALL, segnalatore di una situazione di pericolo. Appunto per questo nelle rappresentazioni grafiche che seguiranno si mostreranno più soluzioni.

Page 12: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

AUTOMI A STATI FINITI ____________________________________________________________________________12

© Virgilio AUTOMI_A_STATI_FINITI

T/”Terra”1P/“Primo“

ALL/”SOS” 2P/“Secondo”

S0

2P/“Secondo” T/”Terra”T/”Terra” 1P/“Primo“

T/”Terra”S1 S2 T/”Terra” 1P/“Primo“ ALL/”SOS” ALL/”SOS”

2P/“Secondo” In questa prima soluzione abbiamo interpretato il pulsante ALL come comando che attiva un’uscita di “SOS” senza spostare l’ascensore dal piano.

1P/“Primo“

1P/“Primo“

ALL/”T&S” ALL/”T&S”

T/”Terra”

2P/“Secondo”

2P/“Secondo”

2P/“Secondo”

1P/“Primo“

T/”Terra”T/”Terra”

ALL/”T&S”

S2 S1

S0

In questa seconda soluzione premendo pulsante ALL, l’ascensore torna al piano terra con segnalazione d’allarme. Si è modificato il simbolo d’uscita in caso di allarme che ora è T&S ad indicare che insieme all’azione di riportare l’ascensore al piano terra va comunque segnalata l’anomalia Terminata la sintesi proviamo a migliorare la “leggibilità” del nostro diagramma: l’indicazione Sx all’interno dei tre cerchi non è proprio autoesplicativa sostituiamola con nomi più adatti tipo TERRA-PRIMO-SECONDO oppure con 0-I°-II°,. Oppure:

Page 13: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

AUTOMI A STATI FINITI ____________________________________________________________________________13

T/”Terra” ALL/”T&S”

1P/“Primo“ 2P/“Secondo”

T ALL/”T&S” ALL/”T&S”

I° II° 2P/“Secondo” 1P/“Primo“

1P/“Primo“ T/”Terra”T/”Terra”

© Virgilio AUTOMI_A_STATI_FINITI

ome nuova considerazione da fare, c’è il fatto che il mezzo meccanico che fa muovere un ascensore non è ltro che un motore che compie un’azione d’avvolgimento o di svolgimento di un cavo in modo da far salire e cendere l’ascensore; appunto per questo l’automa rappresentato non deve far altro che comunicare al otore se salire o scendere, e di quanto.

di un piano ni

soddisfatti per il diagramma così ottenuto, senza mai dimenticare che quella ibili soluzioni. grafica dell’automa attraverso un diagramma degli stati;

rma gabellare utilizzando la tabella di transizione degli stati e di

2P/“Secondo” CasmProviamo a codificare con alcuni simboli i comandi da trasmettere al motore: F Fermo S Sali di un piano SS Sali di due piani G Scendi GG Scendi di due pia Finalmente possiamo ritenerci

tro ata è una delle possda noi vossono, p

Dalla rappresentazione grafica appena terminata è possibile descrivere l’automa come quintupla (secondo Mealy) elencando l’insieme dei simboli d’ingresso , l’insieme de simboli di’uscita , l’insieme degli stati

I = { T, 1P, 2P, ALL } O = {F, S, SS, G, GG} S = {0, I°, II°} E le funzioni δ, ω descritte in fotrasformazione dell’uscita S I T 1P 2P ALL

”S” II°/”SS” 0/”F” 0 0/”F” I°/

I° 0/”G” I°/”F” II°/”S” 0/”G”

II°

• •

0/”GG” I°/”G” II°/”F” 0/”GG” Come leggere questa tabella è intuitivo:

Sulle righe ci sono gli stati Sulle colonne ci sono i possibili segnali di ingresso

ibile comprendere come dallo stato I con ingresso 2P si vada ri quest’ultimi situati all’incrocio tra la riga con etichetta I e la colonna

Posizionandosi su di una riga è possnello stato II con uscita S, valocon etichetta 2P .

Page 14: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

AUTOMI A STATI FINITI ____________________________________________________________________________14

© Virgilio AUTOMI_A_STATI_FINITI

AUTOMA NON DETERMINISTICO ROBABILISTICO

[P ] È in grado di descrivere il comportamento di sistemi in cui in corrispondenza di un ingresso possono esistere più valori ammissibili in uscita (relazioni piuttosto che funzioni tra ingressi e uscite) QUALE MODELLO? • Si adotta un approccio stocastico e il meccanismo di scelta viene precisato tramite l'effettuazione di esperimenti casuali che seguono leggi probabilistiche date e perciò note • La differenza tra un automa deterministico e un automa probabilistico sta perciò nel fatto che nel primo lo stato futuro è noto con certezza, mentre nel secondo viene determinato tramite un esperimento casuale • Per l'automa probabilistico viene precisato il meccanismo, in questo caso stocastico, di scelta In un automa probabilistico le transizioni in uscita da ogni stato sono associate a valori che rappresentano la probabilità con cui ciascuna viene percorsa (Chiaramente somma dei valori rappresentati sugli degli archi in uscita da uno stato deve essere pari a 1)

Page 15: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

AUTOMI A STATI FINITI ____________________________________________________________________________15

© Virgilio AUTOMI_A_STATI_FINITI

Esempi di AUTOMA

• Un automa per contare la parità/disparità delle occorrenze di un simbolo all’interno di una stringa di

ato simbolo e controlla il funzionamento di un frullatore

simboli • Un automa contatore mod M: un sistema che conti , modulo M, le occorrenze di un d• Un automa ch• Un automa che controlla il funzionamento di una porta elettrica • Un automa riconoscitore di sequenze • Un automa che controlla il meccanismo di movimento di un ascensore • Un analizzatore lessicale • Un automa che controlla il funzionamento di un distributore

Page 16: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

AUTOMI A STATI FINITI ____________________________________________________________________________16

© Virgilio AUTOMI_A_STATI_FINITI

:

ESERCIZ

Com inNel so :

ESECIZI

IO1:

b azione di una cassaforte: produce un 1 in uscita ogni volta che riconosce la stringa 110. la luzione proposta c’è un errore provate ad individuarlo

ESERCIZIO 2:

Page 17: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

AUTOMI A STATI FINITI ____________________________________________________________________________17

© Virgilio AUTOMI_A_STATI_FINITI

ONCLUSIONI C

ltro è un automa ?

Certo che lo è! Anzi ,come capiremo presto, trattasi di una macchina programmabile capace di risolvere diversi problemi cambiando il programma.

GRAFO

L’automa risolve un problema preciso, per risolvere un problema diveMa allora il nostro PC, che risolve una vasta gamma di problemi, non

rso bisogna progettarne un a

Page 18: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

AUTOMI A STATI FINITI ____________________________________________________________________________18

APPENDICE A RODOTTO CARTESIANO TRA INSIEMI P

Dati due oggetti a e b, consideriamo un nuovo oggetto; la scrittura (a,b) si chiama coppia ordinata di a e b,

=c e b=d;

(a, b) ≠ (b,a) a meno che a=b.

Dati due insiemi A e B, si chiama prodotto cartesiano

a è detta prima coordinata e b è detta seconda coordinata. Valgono le seguenti proprietà:

1) (a,b) = (c,d) se e soltanto se a

2)

di A e B e lo si indica A x B l'insieme così definito: A x B = { (a, b) | a ∈ A e b ∈ } Formato da tutte le possibili coppie ordinate il cui primo elemento appartiene all’insieme A ed il secondo all’insieme B In generale si ha che A x B ≠ B x A come discende dalla proprietà 2. Nota 1 È importante sottolineare che nelle definizioni di coppia ordinata e prodotto cartesiano è fondamentale l'ordine con cui si scrivono gli oggetti e gli insiemi. Anche in questo caso si generalizza la definizione di prodotto cartesiano a 3 o più insiemi. ESEMPI:

Se A={ 1,2 } e B = { 1, 2, 3}

si ha

A x B ={ (1,1),(1,2),(1,3),(2,1),(2,2),(2,3) } B x A = {(1,1),(2,1),(3,1),(1,2),(2,2),(3,2) } 2) Se il prodotto viene effettuato a partire da tre insiemi che possono anche coincidere

A3 =A x A x A si avrà un insieme formato da triple ordinate Mentre generalizzando si ottiene :

A n = A x A x A x …..x A n volte

Cioè un insieme formato da n-ple ordinate

© Virgilio AUTOMI_A_STATI_FINITI

Page 19: AUTOMI A STATI FINITIisissitinfo.altervista.org/materiale/AUTOMI_A_STATI...MEALY MOORE I h S i /O p S j /o y I h /o k S I S J Se c’è una transizione dallo stato s i allo stato s

AUTOMI A STATI FINITI ____________________________________________________________________________19

© Virgilio AUTOMI_A_STATI_FINITI

APPLICAZIONE O FUNZIONE Dati due insiemi A e B chiamiamo funzione o applicazione da A in B ogni legge (corrispondenza) che associa ad ogni elemento di A uno ed uno solo elemento di B. Si scrive:

BAf →= oppure BA f→ opure

)(xfyx =α

A si chiama dominio o insieme di definizione o range di f e si indica anche con Df. L'insieme B si chiama insieme di arrivo o condominio. o corange di f

Ax∈ è detta variabile indipendente o argomento. By∈ è detta variabile dipendente o valore o immagine di x.

L'insieme BAxxfyByAf ⊂∈=∈= }),(|{)(

è detto codominio o insieme dei valori o insieme delle immagini di f. Ad esempio se A={1,2,3,4}e B={1,2,3,4,5} si può definire la funzione f mediante assegnazione diretta delle

immagini degli elementi di A: 2)4(,3)3(,1)2(,1)1( ==== ffff

ottenendo come condominio

}3,2,1{)( =Af Figura 1: esempio di rappresentazione grafica di una funzione.

Esempi: La legge che ad ogni italiano associa il suo gruppo sanguigno è una funzione: };0,,,{}|{: BABAitalianounèxxIf →= } Data la funzione BAf →: , chiamiamo grafico di f l'insieme Gf definito da )}(|),{( xfyAxByxG f =∈=

1 2

3 4

1 5

24

3

)(Af

f


Recommended