Automi a stati finiti: appunti

tramite: O2O
Difficoltà: media
16

Introduzione

Lo studio della modellizzazione prevede la conoscenza approfondita e dettagliata di quelle che vengono definite le basi dell'informatica. L'informatica è infatti la materia che sta alla base di tutto ciò che ruota attorno alla progettazione ed in particolar modo alla programmazione, branca dell'informatica che abbraccia ormai tutti gli ambiti dell'elettronica. Alla base della modellizzazione e della programmazione vi è infatti la conoscenza di quelli che vengono chiamati automi a stati finiti: vediamo assieme alcuni appunti!

26

Premessa

Prima di iniziare ad introdurre questo argomento vorrei ricordarvi che si tratta di un argomento piuttosto complesso e questa guida non vuole e non può essere del tutto esaustiva, per questo motivo vi consiglio di approfondire lo studio e vi indirizzo ad un sito internet che tratta tale argomento in maniera più dettagliata.

36

Le cifre

Un automa a stati finiti è un sistema composto da una serie ben precisa di elementi, a loro volta semplici o complessi. Innanzitutto esso prevede la presenza di un insieme finito, (cioè costituito da un numero limitato di elementi), di simboli di input, questo insieme lo puoi chiamare I (ad esempio l'insieme I può contenere le due cifre del sistema binario 0 e 1). Poi un automa a stati finiti prevede un insieme (anch'esso finito), di stati, che chiami S (ad esempio s0, s1, s2, s3, s4 e s5). Gli stati corrispondono alle situazioni statiche in cui l'automa, in un certo istante, si trova.
Sempre con riferimento all'insieme S degli stati, un'altra caratteristica di questo sistema è l'identificazione di uno stato cosiddetto 'iniziale', di nome S0 che appartiene naturalmente sempre a S. Normalmente affermi che S0=s0. Poi hai l'insieme degli stati finali, che denomini F, con F ancora sottoinsieme di S (ad esempio F, nel nostro esempio, può essere composto da s4 e s5). A questo punto della definizione, sei giunto all'elemento forse più importante di un automa a stati finiti: l'insieme T delle transizioni.

Continua la lettura
46

La transazione

Una transizione t (elemento di T), è un'azione che associa a ciascuna coppia di stato di partenza e simbolo corrente in input, coppia che denomini formalmente (sip, ii) in quanto elementi -rispettivamente- di S e I, uno stato di arrivo, simboleggiato dalla stringa 'sia' (dalle lettere iniziali di 'simbolo di input di arrivo'). Consideriamo e spieghiamo un paio di transizioni. Sia t0 la transizione che dalla coppia (s0, 0) conduca allo stato s1 e sia t1 la specifica transizione che 'associa' alla coppia (s1, 0) lo stato s2 e t2 la transizione che consente, partendo dalla coppia (s1, 1), di raggiungere lo stato s5 (che è uno stato finale). Sinteticamente puoi renderti conto che, partendo obbligatoriamente per definizione dallo stato s0, se leggi come simbolo corrente 0 approdi allo stato s1. Da questo poi, se leggi come prossimo simbolo ancora uno 0, giungi allo stato s2 e prosegui con l'applicazione di un'altra transizione, invece se da s1 leggi un 1 approdi allo stato s5, il quale essendo uno stato finale ti fa terminare l'analisi della sequenza di simboli in ingresso al tuo automa a stati finiti. Quando raggiungi, a partire da s0, uno stato finale puoi affermare che la sequenza dei simboli di input via via letti (per convenzione da sinistra a destra), è stata 'accettata' dal particolare automa a stati finiti utilizzato.

56

Guarda il video

66

Consigli

Alcuni link che potrebbero esserti utili:

Potrebbe interessarti anche

Segnala contenuti non appropriati

Tipo di contenuto
Devi scegliere almeno una delle opzioni
Descrivi il problema
Devi inserire una descrizione del problema
Si è verificato un errore nel sistema. Riprova più tardi.
Segnala il video che ritieni inappropriato
Devi selezionare il video che desideri segnalare
Verifica la tua identità
Devi verificare la tua identità
chiudi
Grazie per averci aiutato a migliorare la qualità dei nostri contenuti

Guide simili

Università e Master

Appunti di diritto europeo

Il diritto europeo comprende una serie di norme giuridiche che riguardano l'organizzazione dell'Unione Europea ed i suoi rapporti con gli Stati Membri che ne fanno parte. Nella seguente breve guida, potrete trovare gli appunti di diritto europeo e qualsiasi...
Università e Master

Appunti di Storia del Cinema: Hollywood

Il distretto di Hollywood, sito nella parte nord occidentale della città di Los Angeles in California, è noto in tutto il mondo in quanto patria dell'industria cinematografica statunitense. Con i passaggi che seguono ci occuperemo di fornirvi alcuni...
Università e Master

Come riordinare gli appunti dopo la lezione

Gli studenti più meticolosi, che non vogliono perdersi la spiegazione del professore, sono soliti prendere appunti durante una lezione. In questo modo, ripassare a casa risulta essere molto più semplice e pratico. Tuttavia, poiché gli insegnanti tendono...
Università e Master

Come rilegare gli appunti come un libro

Gli appunti sono un elemento fondamentale per tutte quelle persone che sono chiamate ad assistere a delle lezioni, ad una conferenza oppure semplicemente ad una formazione di lavoro e molto spesso rappresentano un vero e proprio dilemma perché vengono...
Università e Master

Appunti di sociolinguistica

In questa guida, che vogliamo proporre a tutti voi, abbiamo deciso di mettere a disposizione dei nostri lettori degli importanti appunti di sociolinguistica, in modo che possano essere utilizzati come meglio si crede e quando ne sia necessario.La sociolinguistica...
Università e Master

Appunti di zoologia

La zoologia è una scienza affascinante e coinvolgente. Questa disciplina studia gli animali e la loro evoluzione. La comprensione della nascita della vita ed il suo evolversi è il metodo più adeguato per la scoperta delle sue origini. La guida di oggi...
Università e Master

Appunti di sociologia dei consumi

Per chi compie i propri studi in ambito sociologico, mettiamo a disposizione alcuni appunti relativi alla materia della sociologia dei consumi. Saranno utili per comprendere come individuare l'utilizzo sociale degli oggetti volti al soddisfacimento dei...
Università e Master

Appunti di diritto pubblico

Per affrontare qualsiasi esame di giurisprudenza, non si può mancare un approfondito studio dei due temi principali della materia: il diritto pubblico ed il diritto privato.Con una buona conoscenza di queste due materie, risulterà notevolmente più...
I presenti contributi sono stati redatti dagli autori ivi menzionati a solo scopo informativo tramite l’utilizzo della piattaforma www.o2o.it e possono essere modificati dagli stessi in qualsiasi momento. Il sito web, www.o2o.it e Arnoldo Mondadori Editore S.p.A. (già Banzai Media S.r.l. fusa per incorporazione in Arnoldo Mondadori Editore S.p.A.), non garantiscono la veridicità, correttezza e completezza di tali contributi e, pertanto, non si assumono alcuna responsabilità in merito all’utilizzo delle informazioni ivi riportate. Per maggiori informazioni leggi il “Disclaimer »”.