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

Teorema di Kleene: dimostrazione

Il Teorema di Kleene, prende il nome dal suo inventore e logico matematico Stephen Cole Kleene. Il teorema, è basato su una formula che mette a confronto le classi dei linguaggi di terzo tipo, degli stati finiti e dei linguaggi regolari,...
Superiori

Come risolvere una moltiplicazione tra 2 O più numeri decimali finiti

In questo articolo, che vuole fungere da guida, pratica e veloce, vogliamo aiutare tutti gli studenti a capire ed imparare, come poter risolvere una moltiplicazione tra 2 o più numeri decimali che siano finiti. Cerchiamo di procedere passo passo e di...
Superiori

Come risolvere una divisione tra numeri decimali finiti

I numeri decimali fanno parte della matematica a tutti gli effetti, proprio come accade con i numeri naturali. In particolare, i decimali finiti (per esempio 3.1, 4.2) sono quei numeri che, dopo la virgola, presentano un "determinato" numero di cifre....
Università e Master

Come Costruire La Versione Matriciale Di Un Grafo

I grafi sono strutture matematiche discrete che rivestono interesse sia per la matematica che per un'ampia gamma di campi applicativi. In ambito matematico il loro studio, la teoria dei grafi, costituisce un'importante parte della combinatoria; i grafi...
Superiori

Come coniugare i verbi deponenti in Latino

Mentre in italiano i verbi sono o di forma attiva (es. Io lodo) o di forma passiva (es. Io sono lodato), in latino esistono anche verbi di forma passiva, ma di significato attivo: i verbi deponenti. I grammatici li hanno chiamati così pensando erroneamente...
Superiori

Dimostrazione della continuità di una funzione derivabile

La funzione è una applicazione matematica formata da x argomento o valore della variabile indipendente detto dominio della funzione e y valore della variabile dipendente, detto condominio della funzione. In esami o compiti in classe, spesso capita agli...
Università e Master

Teorema di Eulero (aritmetica modulare): dimostrazione

Questa guida dal titolo "Teorema di Eulero (aritmetica modulare): dimostrazione" si prefigge di dimostrare cos'è. Il Teorema di Eulero può essere considerato in alcuni casi la conseguenza del teorema di Lagrange, che spiegherò in modo dettagliato nei...
Elementari e Medie

Guida a "Marcovaldo" di Italo Calvino

“Marcovaldo ovvero le stagioni in città”, è una raccolta di racconti di Italo Calvino, pubblicata per la prima volta nel 1963 da Einaudi, in una collana di storie per ragazzi. La narrazione si incentra sulla vita di un magazziniere, Marcovaldo...
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 »”.